5-маъруза Йўналтирилган ациклик графлар

5-маъруза

Йўналтирилган ациклик графлар

Йўналитирилган ациклик графлар бир вазифа бажарилгунча аввалгиси бажарилиб бўлинган боғлиқ-ликларни моделлаштиришда жуда мос келади.
Йўналитирилган ациклик графлар чўққилар ва стрелка билан кўрсатилган йўналтирилган қовурғалар (шаҳобчалар)дан ташкил топади. Ҳар бир йўналтирилган қовурға (u,v) кўринишидаги тартиблашган жуфтликни ташкил этади, бу ерда u ва v – чўққилар.
Йуналтирилган ациклик графлар
Йўналтирилган графлар яна бир хоссага эга: бундай граф чўққисидан бир қанча қовурғалардан ўтиб яна ўзига қайтиб келиш мумкин эмас. Бундай йўналтирилган граф ациклик граф деб аталади, чунки уларда «цикллар», яъни чўққидан яна ўзига қайтадиган йўллар мавжуд эмас.
Йуналтирилган ациклик графлар
Топологик саралаш
Йўналтирилган ациклик графнинг топологик саралаши чўққиларни тартиблаштиради. Агар (u, v) йўналтирилган ациклик графнинг қовурғаси бўлса, у ҳолда чизиқли тартиблаштиришда u v дан аввал келади. Топологик саралаш аввалги дарсларда ўтилган саралашдан фарқ қилади.
Топологик саралаш ёрдамида тузиладиган чизиқли тартиблаштириш ягона бўлмаслиги ҳам мумкин.

Топологик графларнинг иФодаланиш усуллари
Дейлик, граф n та чўққи ва m та қовурғага эга бўлсин. Компьютерда графни бир неча усулда ифодалаш мумкин:

• Боғлиқлик матрицалари
• Тартибсиз рўйхат
• Боғлиқлик рўйхати.

Ациклик графнинг саралаш даври– Θ(n+m).

PERT диаграммасидаги
критик йўл
Агар диаграммада иккита топшириқ орасида уларни боғловчи йўл бўлмаса, у топшириқларни бир вақтда (палаллель) бажариш мумкин.
Қуйида келтирилган йўналтирилган аниклик граф PERT (Project Evaluation and Review Technique – тармоқланувчи графиклар қўлланилган лойиҳаларни режалаштириш ва бажаришга кетадиган вақт сарфини баҳолаш усули) диаграммасига мисол бўла олади.
PERT диаграммасидаги
критик йўл
Графдаги йўл чўққилар ва қовурғалар кетма-кетлиги бўлиб, бир чўққидан иккинчисига (ёки аксинча) ўтишга имкон беради. Бошқача айтганда, йўл чўққиларга эга бўлиб, уларга қовурғалар орқали борилади.
PERT диаграммасидаги критик йўл – вазифаларни бажаришга кетадиган вақтлар йиғиндиси энг максимал бўлган йўлдир. Критик йўлда вазифаларни бажариш учун кетадиган вақтлар йиғиндиси параллелланганлик даражасига боғлиқ бўлмайди.
PERT диаграммасидаги
критик йўл
Йўлнинг узунлигини аниқловчи қиймат, қовурғаларга боғлиқ, чўққиларга эмас. Қовурғаларга боғлиқ бўлган бу қиймат унинг оғирлиги деб аталади. Қовурғалари оғирликка эга бўлган йўналтирилган графлар ўлчанган йўналтилиган графлар деб аталади. Йўлнинг оғирлиги, шу йўлда учрайдиган қовурғалар оғирликлари йиғиндисига тенгдир. Демак, оғирликлар чорраҳалар орасидаги масофани англатса, йўлнинг оғирлиги маршрутнинг умумий масофасини англатади.
Эътиборингиз учун рахмат