Amaliy ish №13 Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari Minimal kenglikdagi daraxt. Kruskal algoritmi

AMALIY ISH № 13
Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari
Minimal kenglikdagi daraxt. Kruskal algoritmi
Og'irligi bor yo'naltirilmagan graf berilgan. Ushbu grafning barcha uchlarini bir-biriga bog'laydigan va shu bilan birga barcha mumkin bo'lganlarning eng kichik og'irligiga (ya'ni chekka og'irliklar yig'indisiga) ega bo'lgan shunday qoldiq daraxtini topish talab qilinadi. Bunday qoldiq daraxt minimal kenglikdagi daraxt yoki oddiy minimal kenglikdagi daraxt deb ataladi.
Bu yerda biz minimal kenglikdagi daraxtlar bilan bog'liq bir nechta muhim faktlarni ko'rib chiqamiz, keyin biz Kruskal algoritmini eng oddiy amalga oshirishda ko'rib chiqamiz.
Minimal oraliq xususiyatlar
Agar barcha qirralarning og'irligi har xil bo'lsa, minimal oraliq daraxt noyobdir. Aks holda, bir nechta minimal oraliqlar bo'lishi mumkin (konkret algoritmlar odatda mumkin bo'lgan oraliqlardan biri bilan yakunlanadi).
Kruskal algoritmi. Ushbu algoritm 1956 yilda Kruskal tomonidan tasvirlangan.
Kruskal algoritmi dastlab har bir cho‘qqini o‘z daraxtiga joylashtiradi, so‘ngra bu daraxtlarni asta-sekin birlashtirib, har bir iteratsiyada qaysidir chekkada ikkita ma’lum daraxtni birlashtiradi. Algoritmni boshlashdan oldin barcha qirralar og'irlik bo'yicha (kamaymaslik tartibida) saralanadi. Keyin birlashtirish jarayoni boshlanadi: barcha qirralar birinchisidan oxirgisiga (tartib tartibida) o'tkaziladi va agar joriy chekkaning uchlari turli pastki daraxtlarga tegishli bo'lsa, u holda bu pastki daraxtlar birlashtiriladi va javobga chekka qo'shiladi. Barcha qirralarni sanab o'tish oxirida barcha uchlar bir xil pastki daraxtga tegishli bo'ladi va javob topiladi.
Misol sifatida 8 ta uchga va 14 ta qirraga ega quyidagi graf berilgan:

Bundagi bog’lanishlar:
v_i, u_i, c_i
0 1 4
0 7 8
1 2 8
1 7 11
2 3 7
2 8 2
2 5 4
3 4 9
3 5 14
4 5 10
5 6 2
6 8 6
6 7 1
7 8 7
Bu sonlarni oxirgi ustun bo’yicha saralaymiz:
6 7 1
5 6 2
2 8 2
0 1 4
2 5 4
6 8 6
2 3 7
7 8 7
0 7 8
1 2 8
3 4 9
4 5 10
1 7 11
3 5 14