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 V2, o log V2=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
    Kruskal algorithm. Example AD ir CE yra mažiausio svorio (5), ir AD pasirenkama atsitiktinai
    Kruskal algorithm. Example CE yra mažiausio svorio (5) ir ji nesudaro ciklo
    Kruskal algorithm. Example DF yra mažiausio svorio (6) ir nesudaro ciklo
    Kruskal algorithm. Example 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)
    Kruskal algorithm. Example 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).
    Kruskal algorithm. Example 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.

    Matroidai
    Pirminiai skaičiai
    Trikampiai skaičiai
    Kokiu greičiu skriejame?
    Skaičiai – apžvalga/ pradmenys
    Revoliucija mazgų teorijoje
    Izingo modelis įmagnetinimui
    Pagrindinės statistinės sąvokos
    Da Vinči matematinė klaidelė
    Žvaigždžių virš Babilono funkcija
    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