11-маъруза Йўналтирил маган графлар

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.

algoritmlar

• Primo algoritmi
• Kraskala (Kruskala) algoritmi
• Boruvka algoritmi

Primo algoritmi

• algoritm dastlab 1930 yilda chesh matematigi Voysex Yarnik tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib chiqilgan va ulardan tashqari E. Deykstra tomonidan 1959 yilda ishlab chiqilgan.
• Algoritm kirishiga yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.
• Algoritm natijasi bo’lib minimal narxli daraxt tugunlari to’plami xisoblanadi
• minimal narxli daraxtlarni xosil qilishda xalqa paydo bo’lishiga yo’l qo’ymaslik kerak