Kruskalov algoritmus - konštrukcia optimálneho kostra

Začiatkom 19. storočia geometer z Berlína Jacob Steiner stanovil úlohu spojiť tri dediny tak, aby ich dĺžka bola najkratšia. Následne zovšeobecnil tento problém: je potrebné nájsť bod v rovine tak, že vzdialenosť od nej do iných bodov bola najmenšia. V 20. storočí pokračovali práce na tejto téme. Rozhodlo sa, že si vezmeme niekoľko bodov a spojíme ich tak, aby vzdialenosť medzi nimi bola najkratšia. To je všetko špeciálny prípad skúmaného problému.

Chamtivé algoritmy

Kruskalov algoritmus sa vzťahuje na algoritmy "chamtivosti" (nazývajú sa tiež gradientné algoritmy). Podstata tých - najväčšie víťazstvo na každom kroku. Nie vždy algoritmy "chamtivosti" poskytujú najlepšie riešenie úlohy. Existuje teória, ktorá ukazuje, že pri použití na konkrétne problémy poskytuje optimálne riešenie. Toto je teória matroidov. Kruskal algoritmus sa týka takýchto problémov.

Nájdenie kostry s minimálnou hmotnosťou

Uvažovaný algoritmus konštruuje optimálnu kostru grafu. Problém o tom je nasledovný. Zobrazí sa neorientovaný graf bez viacerých okrajov a slučiek a na jeho súprave okrajov sa uvádza funkcia hmotnosti w, ktorá priradí každému okraju e číslo - hmotnosť okraja - w (e). Hmotnosť každej podmnožiny množiny okrajov je určená súčtom závaží okrajov. Je potrebné nájsť kostru s najmenšou hmotnosťou.

popis

Kruskal algoritmus funguje takto. Po prvé, všetky okraje pôvodného grafu sú usporiadané v poradí zvyšujúcich sa váh. Na začiatku rámec neobsahuje žiadne hrany, ale obsahuje všetky vrcholy grafu. Po ďalšom kroku algoritmu sa do už vytvorenej časti rámca pridáva jedna hrana, čo je ležiaca lesa. Nie je ľubovoľne zvolený. Všetky okraje grafu, ktoré nepatria do kostry, je možné označiť ako červenú a zelenú. Vrcholy každého červeného rebra sú v jednej zložke spojitosti lesa, ktorý je konštruovaný a vrcholy zelene sú v rôznych zložkách. Preto ak tam pridáte červený okraj, objaví sa cyklus a ak sa zelený objaví vo výslednom lesnom kroku, pripojený komponent bude menej o jednu. Preto nie je možné do výslednej konštrukcie pridať žiadnu červenú hranu, ale na získanie lesa sa dá pridať ľubovoľná zelená hrana. A pridá sa zelené rebro s minimálnou hmotnosťou. Výsledkom je rám s najmenšou hmotnosťou.

uskutočnenie

Označujeme súčasný strom F. Rozdeľuje množinu vrcholov grafu do pripojených domén (ich spojovacie formy F a nekontaktujú sa v pároch). Červené okraje majú oba vrcholy v jednej časti. Časť (x) je funkcia, ktorá vracia názov časti, ku ktorej x patrí pre každý vrchol x. Spoj (x, y) je postup, ktorý vytvára nový oddiel pozostávajúci z spojenia častí x a y a všetkých ostatných častí. Nechť n je počet okrajov grafu. Všetky tieto pojmy sú zahrnuté v algoritme Kruskal. realizácie:

1. Usporiadajte všetky okraje grafu od 1. až po n-stúpajúcu hmotnosť. (Ai, bi sú vrcholy hrany s indexom i).

2. Pre i = 1 až n.

3. X: = Časť (ai).

4. Y: = časť (bi).

5. Ak x nie je rovno y, potom Unite (x, y), zahrňte okraj s číslom i v F.

korektnosť

Nech T je kostra pôvodného grafu vytvoreného pomocou Kruskalovho algoritmu a S nech je jeho ľubovoľná kostra. Je potrebné preukázať, že w (T) neprekračuje w (S).

Nech M je súbor okrajov S, P množina okrajov T. Ak sa S nerovná T, potom existuje okraj T a T, ktorý nepatrí k S. Pripojíme sa k S. Vytvárame cyklus, nazývame to C. Odstránime od C všetky hrany, ktoré patria S. Nový rám sa dosiahne, pretože obidva okraje a vrcholy v nej sú rovnaké. Jeho hmotnosť nepresahuje w (S), pretože w (et) nie je väčšia ako w (es) algoritmom Kruskal. Táto operácia (výmena okrajov S okrajmi T) sa bude opakovať, kým sa nedosiahne T. Hmotnosť každého nasledujúceho skeletu nie je väčšia ako hmotnosť predchádzajúcej, z čoho vyplýva, že w (T) je najviac w (S).

Tiež správnosť Kruskalovho algoritmu vyplýva z Rado-Edmondovej teorému o matroidoch.

Príklady použitia algoritmu Kruskal

Graf s vrcholmi a, b, c, d, e a okrajmi (a, b), (a, e), b, c, b, , (D, e). Hmotnosti okrajov sú uvedené v tabuľke a na obrázku. Spočiatku zostrojený les F obsahuje všetky vrcholy grafu a neobsahuje jediný okraj. Kruskalský algoritmus najprv pridá okraj (a, e), pretože jeho váha je najmenšia a vrcholy a a e sú v rôznych zložkách spojenia lesa F (okraj (a, e) je zelený), potom okraj (c, d) Aby tento okraj mal najmenšiu váhu od okrajov grafu, ktorý nepatrí do F a je zelený, potom sa z rovnakých dôvodov pridá okraj (a, b). Ale okraje (b, e) sú preskočené, aj keď majú najmenšiu váhu zvyšných okrajov, pretože sú červené: vrcholy b a e patria k tej istej zložke spojitosti lesa F, to znamená ak pridáme okraj (b, e) do F, cyklus. Potom sa pridá zelená hrana (b, c), červená hrana (c, e) sa preskočí a potom d, e. Preto sa postupne pridávajú okraje (a, e), (c, d), (a, b), (b, c). Z nej je optimálny skelet pôvodného grafu. Takto algoritmus funguje v tomto prípade Obaroval som. Príklad ukazuje toto.

Obrázok znázorňuje graf pozostávajúci z dvoch pripojených komponentov. Tučné riadky zobrazujú okraje optimálneho rámca (zelené), vytvorené pomocou algoritmu Kruskal.

V hornej časti je zobrazený počiatočný graf a na dolnej časti - kostra minimálnej hmotnosti, ktorá bola pre ňu vytvorená pomocou uvažovaného algoritmu.

Sekvencia pridaných okrajov: (1.6); (0,3), (2,6) alebo (2,6), (0,3) - nezáleží; (3,4); (0,1), (1,6) alebo (1,6), (0,1) je tiež ľahostajný (5,6).

Kraskalov algoritmus nájde praktickú aplikáciu napríklad na optimalizáciu komunikačných podložiek, ciest v nových mikrodistroch v lokalitách každej krajiny, ako aj v iných prípadoch.