O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

Minimal narxli daraxtlar skeleti

Minimal narxli skeletni topish masalasi ko’pincha quyidagicha xolatlarda uchraydi: masalan, n ta shaxar mavjud va ular orasiga yo’llarni shunaqa qurish kerakki, istalgan shaxardan ixtiyoriy boshqasiga bevosita yoki bilvosita borish mumkin bo’lsin va ular orasiga yo’l qurish sarf xarajatlari ma’lum bo’lsin. Yo’llarni qurishni shunday rejalashtirish kerakki, natijada sarf xarajat minimal bo’lsin.

3-rasm. Vaznga ega bo’lgan yo’naltirilmagan graf.

Bu masala graflar nazariyasida minimal narxli daraxt skeleti (ostovnoye derevo) deb nomlanadi.

Ushbu masalani yechishning bir qator algoritmlari mavjud:

1. 
   Primo algoritmi
   
2. 
   Kraskala (Kruskala) algoritmi
   
3. 
   Boruvka algoritmi