7-маъруза бошқариш тизимларининг структуравий таҳлилида графлар назарияси

7-МАЪРУЗА
БОШҚАРИШ ТИЗИМЛАРИНИНГ СТРУКТУРАВИЙ ТАҲЛИЛИДА ГРАФЛАР НАЗАРИЯСИ
Структурани граф шаклида ифодалаш тамойили жуда оддий. Баъзи муаммоларни ечишда тизимнинг элементи граф қирралари билан, боғланишлар эса - граф чўққилари билан тасвирланади. Айрим масалаларда эса улар аксинча: элементлар граф чўққилари билан, боғланишлар эса граф қирралари билан ифодаланади. Биринчи ҳолда ҳосил қилинган граф қиррали, иккинчи ҳолатда - чўққили граф деб номланади.
Катта бошқариш тизимларини структуравий таҳлил қилиш масалаларида графларнинг бир неча тушунча ва таърифларини кўриб чиқамиз.
Граф тушунчаси, графларнинг турлари. Бир неча элементлар тўплами берилан бўлсин. Агар тўпламга тегишли элементлар орасидаги боғланилар мавжуд бўлса, граф аниқланган ҳисобланади. Геометрик интерпретацияга мос равишда графнинг қирраси, лар эса графнинг чўққилари деб аталади. Агар чўққиларнинг ёзилиш тартиби аҳамиятли бўлмаса, яъни , у ҳолда қирра йўналтирилмаган қирра ҳисобланади. Акс ҳолда эса йўналтирилган қирра ёки йўналтирилган ёй дейилади. Графлар назариясида қуйидаги терминология ҳам қабул қилинган: агар қирра чўққиларга нисбатан инцидиент бўлса, чўққилар ҳам қиррага нисбатан инцидиент ҳисобланади. Фақат йўналтирилмаган қирралардан иборат граф – йўналтирилмаган граф, фақат йўналтирилган қирралардан тузилган граф эса йўналтирилган граф деб аталади. Агар граф ҳам йўналтирилмаган ҳам йўналтирилган қирралардан иборат бўлса, у аралаш граф деб номланади. Йўналтирилмаган графни иккилантириш жараёни ёрдамида йўналтирилган графга айлантириг мумкин. Бунинг учун ҳар бир йўналтирилмаган қирраларни иккита бир-бирига қарама-қарши йўналтирилган қирраларга алмаштириб чиқиш зарур бўлади. Агар графнинг қирралари чекли бўлса, у чекли граф деб аталади, акс холда эса у чекланмаган граф дейилади. Изоляцияланган чўққилардан иборат граф нуль-граф дейилади. Иккита турли чўққилар орасида мумкин бўлган барча қирралар мавжуд бўлса, бундай граф тўлиқ граф дейилади. Йўналтирилган тўлиқ графларда ҳар бир йўналиш бўйича иҳтиёрий иккита чўққиларни бирлаштирувчи жуфт қирралар мавдул бўлади.
1953 йилда Меэсон томонидан чизиқли алгебраик тенгламалар билан ёзиладиган тизимларда қурилмаларнинг ўзгарувчилари орасидаги боғланишларни визуал ифодалаш учун сигналлар графини ишлаб чиққан. Лаплас тасвирларида стационар чизиқли бошқариш тизими чизиқли алгебраик тенгламалар тизими билан ҳам тасвирланганлиги сабабли, сигнал графи бошқариш тизимларини тавсифлаш учун ишлатила бошланди ва бошқариш тизими графиги деб номланди.
Бошқариш тизимининг графи мураккаб кўп циклли тизимларнинг структуравий диаграммаларини олдиндан ўзгартирмасдан узатиш функцияларини ҳисоблаш имконини бергани учун ундан фойдаланиш жуда қулайдир.
Бошқариш тизимининг графи ҳам ёй ва чўққилардан иборат бўлади. Ёй схемада кўрсаткичли тўғри ёки эгри чизиқ билан ифодаланади ва бу кўрсаткич сигналнинг йўналишини билдиради. Бошқариш графларидаги ёйлар структура схемасидаги звеноларга мос келади. Яъни, ҳар бир ёй ўзининг узатиш функциясига эга бўлади. Ёй чўққилар билан бошланади ва чўққилар билан якунланади.
Чўққилар схемада нуқталар ёкит айланалар кўринишида тасвирланади ва ўзгарувчиларни ифодалайди. Агар чўққидан битта ёй чиқадиган бўлса, бу чўққи ёрдамида ёйнинг кириш ўзгарувчиси ифодаланган бўлади. Агар битта ёй битта чўққига борса, Бу ёйнинг битта чиқиш ўзгарувчиси тасвирланганлигини англатади (7.1,а-расм). Агар битта чўққига бир нечта ёйлар йўналтирилган бўлса, чўққи билан ифодаланган ўзгарувчининг қиймати унга йўналтирилган ёйлар билан ифодаланган узатиш функциялари чиқиш қийматларининг йиғиндисига тенг деб қаралади (7.1,б-расм). Агар битта чўққидан бир нечта ёйлар чиқаётган бўлса, чўққи билан ифодаланган ўзгарувчи шу чўққидан чиқувчи ёйлар билан ифодаланган барча узатиш функциялари учун кириш сигнали бўлиб хизмат қилади (7.1,в-расм).

7.1-расм. Ёйлар ва чўққиларнинг боғланиш турлари
Ёйнинг бошланғич чўққиси унинг кириш ўзгарувчисини аниқлайди. Фақат чиқиш ёйлари билан боғланган чўққилар ташқи ўзгарувчиларни (ташқи таъсирларни) ттасвирлайди ва графнинг кириш қирралари деб номланади.
Бошқариш тизимнинг графида ёйлар ва уларнинг операторларини, шунингдек, қирралар ва уларга мос бўлган ўзгарувчиларни белгилаш учун турли индексли бир хил харфлардан фойдаланилади. Аниқроқ қилиб айтганда, «W ёй» ҳамда «x чўққи» белгиланишлари остида W - ёйнинг идентификаторини, x – ўзгарувчининг идентификаторини билдиради.
ёйлар кетма-кет уланганда - ёйнинг якуний қирраси ўзидан кейинда турган – ёйга кириш сигнали сифатида узатилади. Бундай холда ёй йўналтирилган ёй ёки ормаршрут деб аталади. Агар ёйнинг якуний қирраси ёйнинг бошланғич қирраси билан устма уст тушса ва бўлса, бундай ормаршрут берк контурли ҳисобланади. Акс холда ормаршрут очиқ контурли ҳисобланади.
Такрорланувчи ёйлари бўлмаган (яъни, барча ёйлари турли хил) ормаршрут очиқ бўлса, бошланғич қиррадан якуний қиррагача йўл деб номланади. Агар у ёпиқ бўлса контур деб аталади. Агар барча қирралар турлича бўлса, йўл ва контур содда йўл ва контур деб аталади. Содда йўл тўғри йўл деб ҳам юритилади.

7.2-расм. Ормаршрутлар, йўллар, тўғри йўллар.
7.2-расмда келтирилган графикда бошланғич қиррадан охириги қиррагача учта йўл мавжуд бўлиб, булар қуйидагилар:



Булардан ва тўғри йўл ҳисобланади. Юқоридаги расмда орграфлар сони тўртта. Юқорида келтирилган йўллардан ташқари қуйидаги ормаршурт ҳам мавжуд:

Икки контурнинг умумий учлари бўлмаса, қўшни бўлмаган дейилади. Шубҳасиз, қўшни бўлмаган контурларда умумий ёйлар бўлиши мумкин эмас. Уч, тўрт ва бошқа контурлар агар уларнинг бирон бир жуфти қўшни бўлмаса, қўшни бўлмаган контурлар деб аталади.

а)	б)
7.3-расм. Бошқприш тизимининг структура схемасини графга айлантириш

Бошқариш тизимининг графигини унинг структура схемаси асосида ёки аксинча, структура схемасини унинг графи асосида қуриш мумкин.

Структура схемаси асосида бошқариш тизимининг графини қуриш учун қуйидаги белгилашларни киритиб олиш зарур:

1. 
   кириш ўзгарувчисига эга бўлган сумматор чўққи билан алмаштирилади.
   
2. 
   узатиш функцияси ёй билан алмаштирилади. Агар узатиш фунциясининг чиқиш ўзгарувчиси сумматорга манфий ишора билан келса, звенонинг ишораси манфийга ўзгартирилади ( ).
   
3. 
   Ҳар бир ўзгарувчи, шунингдек, ташқи таъсирни ифодаловчи ўзгарувчи ҳам чўққилар билан ифодаланади. Кириш ўзгарувчилари эса кириш қирраларига эга бўлмаган чўққилар сифатида тасвирланади.
   

Агар умумий чўққига келувчи бир неча ёйлардан бирининг чиқиш ўзгарувчисини тасвирлаш керак бўлса, қирранинг чиқишига қўшимча чўққи киритилади ва бу чўққидан бирлик ёй чиқариб, кейинги чўққи билан боғланади (7.4-расм).

а)	б)
7.4-расм. Қўшимча чўққини тасвирлаш учун графни ўзгартириш

Параллел ёйлар, яъни умумий бошланғич ва охирги қирраларга эга бўлган ёйлар, мазкур ёйларнинг узатиш функциялари йиғиндисига тенг бўлган узатиш функцияси орқали ифодаланувчи битта ёй билан алмаштирилиши мумкин (7.5-расм, а).

а)

б)

7.4-расм. Графларни ўзгартириш: а-параллел боғланиш, б-содда йўл

Агар содда йўлнинг қирралари орасидаги чўққиларга кириш ёки чиқиш қирралар йўналтирилмаган бўлса, уни содда йўлни ташкил этувчи қирралар узатиш функцияларининг кўпайтмасидан иборат узатиш функцияси билан ёзиладиган битта йўлга алмаштириш мумкин (7.4,б-расм).
Графни ўзгартириш ва унинг графидан бошқарув тизимининг узатиш функциясини ҳисоблаш учун Мейсон теоремасидан (формуладан) фойдаланиш мумкин. Аммо уни шакллантириш учун графнинг аниқловчиси деб номланувчи қўшимча тушунча билан танишиш керак.