Режа: Минимал нархли дарахтлар склети

Hash tables. Graph ma’lumotlar tuzilmasi. Breadth-First search algoritmi


Режа:

1. 
   Минимал нархли дарахтлар склети
   
2. 
   Прим алгоритми
   
3. 
   Краскал алгоритми
   

Минимал нархли дарахтлар склети. G=(V, Е) – боғланган граф бўлсин, унда ҳар бир (v, w) қирра қирралар нархи деб аталувчи c(v, w) рақам билан белгиланган. G графнинг дарахтлар склети деб, шу графнинг барча V тугунларини ўз ичига олган бўш дарахтга айтилади. Дарахтлар склети нархи шу дарахтга кирувчи барча қирралар йиғиндиси сифатида ҳисобланади. Биз минимал нархли дарахтлар склетини топиш масаласини кўрамиз.
Мисол. 1-расмда граф ва унинг минимал нархли дарахтлар склети келтирилган.

1-расм. Граф ва унинг дарахтлар склети

Минимал нархли дарахтлар склетига типик мисол қилиб, коммуникацион тармоқларни олиш мумкин. Бу ерда граф тугунлари шаҳарларни, қирра – эса шаҳарлар орасида бўлиши мумкин бўлган коммуникацион чизиқлар, қирралар нархини коммуникацоин линияларнинг нархи сифатида қараш мумкин. Бу ҳолда минимал нархли дарахтлар склети барча шаҳарларни бирлаштирувчи минимал нархли коммуникацион тармоқларни ифодалайди.

- Тармоқда маълумотни тарқатиш учун дарахтлар шакллантирилади.
- уйлар ўртасида алоқа кабелини тортиш масаласи (қирра нархи – уйлар орасига кетадиган кабел нархи).
- Ethernet стандарти учун циклларни олдини оладиган Spanning Tree Protocol.


Прим алгоритми.
Ушбу алгоритм Роберт Прим томонидан 1957 йили ишлаб чиқилган. Унгача 1930 йили чех математиги Войтек Ярник (Vojtěch Jarník) томонидан, кеийнроқ 1959 йилда Эдгар Дейкстра (Edsger Dijkstra) томонидан ишлаб чикилган.
Минимал нархли дарахтлар склетини қуришнинг иккита кенг тарқалган усули мавжуд. Улардан бири Прим алгоритми. Бу алгоритмда дарахтлар склети «ўсадиган» ("вырастает") U қирралар тўплами қурилади. V={1, 2,..., n} бўлсин. Аввал U={1} бўлади. Алгоритмнинг ҳар бир қадамида минимал нархли қирра топилади, ундан кейин v қирра V\U тўпламдан U тўпламга ўтказилади. Бу жараён U тўплам V тўпламга тенг бўлгунча такрорланади.
Мисол