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.
Prim algoritmi.
Ushbu algoritm Robert Prim tomonidan 1957 yili ishlab chiqilgan. Ungacha 1930 yili chex matematigi Voytek Yarnik (Vojtěch Jarník) tomonidan, keiynroq 1959 yilda Edgar Deykstra (Edsger Dijkstra) tomonidan ishlab chikilgan.
Minimal narxli daraxtlar skletini qurishning ikkita keng tarqalgan usuli mavjud. Ulardan biri Prim algoritmi. Bu algoritmda daraxtlar skleti «o’sadigan» ("vыrastayet") U qirralar to’plami quriladi. V={1, 2,..., n} bo’lsin. Avval U={1} bo’ladi. Algoritmning har bir qadamida minimal narxli qirra topiladi, undan keyin v qirra V\U to’plamdan U to’plamga o’tkaziladi. Bu jarayon U to’plam V to’plamga teng bo’lguncha takrorlanadi.
Misol