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

Kruskal algoritmi

• Algoritm dastlab 1956 yilda Jozef Kruskal tomonidan taklif etilgan.
• Dastlab yoylarning boshlang’ich to’plami bo’sh deb olinadi.
• Keyin, imkoni bo’sa, quyidagi amal bajariladi:
• Mavjud yoylar qarab chiqiladi, ularni daraxtga qo’shganda xalqa xosil bo’lmaydigan bo’lsa, ularning vazni minimali olinadi va daraxtga qo’shiladi.
• Agar bunday yoylar bo’lmasa, algoritm tugallanadi.
• Graf tugunlaridan xosil bo’lgan qismgraf minimal narxli daraxt xisoblanadi.

Algoritmga misol

tasvir	izox
	AD va CE yoylar minimal vaznga ega - 5. ixtiyoriy bittasi tanlanadi., masalan AD
	Keyingi kichikroq yoy 5 - CE. Yoyi xisoblanadi. Uni tanlanganda xalqa xosil bo’lmaydi.
	Vazni 6 ga teng bo’lgan DF yoyi tanlanadi.

Algoritmga misol

tasvir	izox
	AB va BE yoylar vazni 7. AB ni ixtiyoriy tanlaymiz, BD yoy tanlanmaydi, chunki ABD xalqa xosil bo’lishi mumkin.
	Vazni 7 bo’lgan BE yoy tanlanadi. BC yoy olinmaydi, chunki BCE xalqa, DE xam olinmaydi, chunki DEBA xalqa, FE xam olinmaydi, chunki FEBAD xalqa.
	Vazni 9 bo’o’lgan EG yoy qo’shiladi va algoritm tugullanadi. Minimal narxli daraxt aniqlandi.

Kruskal algoritm samaradorligi

• Algoritm boshlanishidan avval yoylarni vazni bo’yicha saralab chiqish talab etiladi. Buning uchun O(E × log(E)) vaqt talab etiladi. Qolgan vaqt yoylarni daraxtga qo’shish uchun sarflanadi.
• Kruskal algoritmida vaqt asosan saralashga sarflanishi sababli samaradorlikni O(E × log(E)) deb olish mumkin.

Mustaqil ish: Boruvka algoritmi va samaradorligi

• Mustaqil ish: Boruvka algoritmi va samaradorligi

Nazorat savollari:

• 1. yo’naltirilmagan graf tushunchalari, qo’shnilar, insident yoy, xalqa
• 2. Graflarni ko’ruvdan o’tkazish algoritmlari va dasturini tushuntiring.
• minimal narxli daraxt skeleti va uni yaratish algoritmlarini qiyosiy taxlili