Prim algoritmi Kraskal algoritmi

5-MA’RUZA.

Mavzu: Graflar ustida algoritmlar

Reja:

1. 
   Minimal narxli daraxtlar skleti
   
2. 
   Prim algoritmi
   
3. 
   Kraskal algoritmi
   

Kalit so’zlar: Graf, minimal narxli daraxt, Prim algoritmi, Kraskal algoritmi

Minimal narxli daraxtlar skleti. G=(V, Ye) – bog’langan graf bo’lsin, unda har bir (v, w) qirra qirralar narxi deb ataluvchi c(v, w) raqam bilan belgilangan. G grafning daraxtlar skleti deb, shu grafning barcha V tugunlarini o’z ichiga olgan bo’sh daraxtga aytiladi. Daraxtlar skleti narxi shu daraxtga kiruvchi barcha qirralar yig’indisi sifatida hisoblanadi. Biz minimal narxli daraxtlar skletini topish masalasini ko’ramiz.

Misol. 1-rasmda graf va uning minimal narxli daraxtlar skleti keltirilgan.

1-rasm. Graf va uning daraxtlar skleti

Minimal narxli daraxtlar skletiga tipik misol qilib, kommunikasion tarmoqlarni olish mumkin. Bu yerda graf tugunlari shaharlarni, qirra – esa shaharlar orasida bo’lishi mumkin bo’lgan kommunikasion chiziqlar, qirralar narxini kommunikasoin liniyalarning narxi sifatida qarash mumkin. Bu holda minimal narxli daraxtlar skleti barcha shaharlarni birlashtiruvchi minimal narxli kommunikasion tarmoqlarni ifodalaydi.

- Tarmoqda ma’lumotni tarqatish uchun daraxtlar shakllantiriladi.

- uylar o’rtasida aloqa kabelini tortish masalasi (qirra narxi – uylar orasiga ketadigan kabel narxi).

- Ethernet standarti uchun sikllarni oldini oladigan Spanning Tree Protocol.