Universitetining jizzax filiali amaliy matematika fakulteti «kompyuter ilmlari va dasturlashtirish»

Minimal narxli daraxtlar skleti.
Graflarni oʻrganish bilan shugʻullanadigan diskret matematikaning boʻlimi 
―Graflar nazariyasi deb ataladi. Graflar nazariyasida ushbu matematik 
obyektlarning asosiy tushunchalari, xususiyatlari, tasvirlash usullari va qoʻllanilish 
sohalari batafsil koʻrib chiqilgan. Bizni faqat dasturlashda muhim boʻlgan jihatlari 
qiziqtiradi. Graflar - bu chiziqlar bilan bogʻlangan nuqtalar toʻplami. Nuqtalar uchlar 
(tugunlar) chiziqlar esa qirralar (yoylar) deb nomlanadi.G=(V, Ye) – bogʻlangan 
graf boʻlsin, unda har bir (v, w) qirra qirralar narxi deb ataluvchi c(v, w) raqam bilan 
belgilangan. 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. 

---

4 
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} 

---

5 
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 
.