Kruskal algoritmi. - Kruskal algoritmi bu yo'naltirilmagan chekka og'irlikdagi grafikning minimal o'rmonini topadi . grafik ulangan bo'lsa, u minimal kenglik daraxtini topadi . (bog‘langan grafikning minimal kenglikdagi daraxti har bir cho‘qqini o‘z ichiga olgan daraxtni tashkil etuvchi qirralarning kichik to‘plami bo‘lib, bu yerda daraxtdagi barcha qirralarning og‘irliklari yig‘indisi minimallashtiriladi. Ajratilgan grafik uchun minimal kenglikdagi o‘rmon hisoblanadi. Har bir ulangan komponent uchun minimal oraliq daraxtdan iborat .) bu grafik nazariyasidagi ochko'z algoritmdir.Har bir qadamda u minimal kenglikdagi o'rmonga tsikl hosil qilmaydigan keyingi eng past og'irlikdagi chekkani qo'shadi. Bu algoritm birinchi marta 1956 yilda amerika matematik jamiyatining 48-50-betlarida paydo bo'lgan va jozef kruskal tomonidan yozilgan . loberman va weinberger (1957) tomonidan qayta kashf etilgan .
- kruskal algoritmi grafning tarmoqlarining minimum spannig tarmoqlari (MST) ni topish uchun ishlatiladigan bir algoritmdir. MST tarmoqqa mos keladigan hamda hamma tarmoqqa kiradigan eng arzon yo'l ulchamini topadi. Bu bir qator ilg'or holda masala hal qilish uchun foydalaniladi.
- Kruskal algoritmi, qurilish va hamkorlik sohasida ham foydalaniladi. Misol uchun, yuqorida aytildigi kabi, tarmoqning minimal tuzilishini topishingiz lozim bo'lgan ishga kirishingiz mumkin, ya'ni bitta ulcham uchun avval bir xil ehtimol chaqirishni sezmish bo'lgach, keyin hech qismini qo'llab-quvvatlamasligingiz kerak.
Kruskal algoritmi hammasi bir misolda ishlatiladi: - Kruskal algoritmi hammasi bir misolda ishlatiladi:
- Graph:
C ----9 ---- D ----8 ---- E /| /| / | 15 | 10 | 11 | | / | / | / | A ----7---- B ----6----F |12 | | | | | | | 5| | 6| | 13 |
Do'stlaringiz bilan baham: |
