Kraskalo algoritmas  

[ Apie naudojamas sąvokas žr. >>>>> ]    

Kraskalo algoritmas - algoritmas grafų teorijoje, nustatantis karkasinį medį jungiame neorientuotame medyje su svoriais. Jei grafas nėra jungus, jis nustato minimalų karkasinį mišką. Tai godaus algoritmo pavyzdys.

Pirmąkart algoritmą aprašė Joseph Kruskal‘as 1956 m. (Proceedings of the American Mathematical Society, pp.48-50). Kiti tam skirti algoritmai yra Primo, atvirkštinis-šalinimo (reverse-delete) ir Boruvkos algoritmai.

Pradžioje turime tuščią aibę. Tada, kol įmanoma, atliekama tokia operacija: iš visų briaunų, kurias įjungus prie jau parinktų, nesusidaro ciklas, išrenkama mažiausio svorio briauna. Kai tokių briaunų nebelieka, algoritmas baigia darbą. Tada pografis, kurį sudaro visos jo viršūnės ir surastos briaunos, sudaro grafo karkasinį medį.

Jei E yra grafo viršūnių kiekis, o V – briaunų kiekis, Kraskalo algoritmo laikas gali būti įvertintas O (E log(E)) arba, kas tas pat, O (E log(V)). Taip yra todėl, kad

E daugiausia gali būti lygus V², o log V²=2 log V = O(log V) [ apie Landau simbolius O ir o žr. >>>>)

jei nekreipsime dėmesio į izoliuotas viršūnes, kurių kiekviena turės savo elementą minimaliame karkasiniame miške, V <= E+1, tad log V= O(log E)

Šis įvertinimas pasiekiamas taip: pirmiausia briaunos surūšiuojamos pagal svorius per O (E log E) laiką – tai leis išrinkti minimalią briauną per pastovų laiką. Tada ciklo patikrinimui ir briaunos įtraukimui sugaištama O(E) laiko. Tad bendras laikas lieka O (E log E).

Pavyzdys:

	AD ir CE yra mažiausio svorio (5), ir AD pasirenkama atsitiktinai
	CE yra mažiausio svorio (5) ir ji nesudaro ciklo
	DF yra mažiausio svorio (6) ir nesudaro ciklo
	AB ir BE yra mažiausio svorio (7). Atsitiktinai pasirenkama AB. Tada BD pažymima raudonai, nes jau yra kelias nuo B iki D, ir susidarytų ciklas ją pasirinkus (ABD)
	BE yra trumpiausia briauna (7), o raudonai pažymimos BC (nes sudarytų ciklą BCE), DE (nes sudarytų ciklą DEBA) ir FE (nes sudarytų ciklą FEBAD).
	Galiausiai procesas baigiamas pasirinkus EG (9)

Algoritmo korektiškumo įrodymas

Įrodymas susideda iš dviejų dalių: 1) kad algoritmas nustato jungiantįjį medį; 2) kad jisai yra minimalaus svorio. Beje, Kraskalo algoritmas yra atskiras Rado-Edmondso algoritmo grafiniam matroidui atvejis.

1. Tegu P yra jungus grafas su svoriais, o Y – P pografis, kurį sudaro algoritmas. Y negali turėti ciklo. Y yra jungus, nes algoritmas įdėtų briauną, jungiančią pomedžius.. Tad Y yra jungiantysis medis.

2. Minimalumas įrodomas indukcijos metodu – kad kiekvieno žingsnio metu yra teisinga, kad išrinktos briaunos priklauso kažkuriam karkasiniam medžiui.

• Pradžioje (tuščiai aibei) tai teisinga, nes bet koks jungus grafas su svoriais turi karkasinį medį.
• Tarkim, kad tai teisinga kažkuriam (ne paskutiniam) žingsniui. Tegu T yra toks karkasinis medis, turintis atrinktas briaunas. Jei naujai parinkta briauna e irgi priklauso T, tai teiginys teisingas naujam rinkiniui su ta briauna. Jei e nepriklauso T, tada T+e turi ciklą C ir yra kita briauna f, esanti cikle C, tačiau nesanti tarp anksčiau parinktų briaunų (jei tokios f nebūtų, tada e negalima būtų pasirinkti, nes susidarytų ciklas C). Tada T-f+e yra medis su tokiu pat svoriu kaip T, nes T yra minimalaus svorio ir f svoris negali būti mažiau už e (nes kitaip būtų pasirinkta f, o ne e).
• Tad sudarytas jungiantysis medis tegali būti karkasinis (t.y. minimalus jungiantysis) medis.

Matroidai
Pirminiai skaičiai
Trikampiai skaičiai
Kokiu greičiu skriejame?
Skaičiai – apžvalga/ pradmenys
Trijų kūnų uždavinys aštuoniukėje
Revoliucija mazgų teorijoje
Izingo modelis įmagnetinimui
Pagrindinės statistinės sąvokos
Da Vinči matematinė klaidelė
Žvaigždžių virš Babilono funkcija
Intuityvus Hafmano kodo paaiškinimas
Faneroskopija prieš fenomenologiją
2014 m. "Abelis" - biliardo teorijos kūrėjas
Simpsonų trauka ir žaidimas skaičiais
Specialioji reliatyvumo teorija
Didžiausias bendras daliklis
Paviliota senovinio žaidimo
Visata kaip kompiuteris
Monte-Karlo metodas
Ar viskas čia taip?
Harmoninės eilutės
Nešo pusiausvyra
Smeilo paradoksas
Dalyba iš nulio
Perkoliacija
Vartiklis