Kruskalův algoritmus - konstrukce optimálního skeletu

Počátkem 19. století nastavil geometr z Berlína Jacob Steiner úkol spojit tři vesnice tak, aby jejich délka byla nejkratší. Následně generalizoval tento problém: je třeba najít bod v rovině tak, že vzdálenost od ní k jiným bodům byla nejmenší. Ve 20. století pokračovalo práce na tomto tématu. Bylo rozhodnuto vzít několik bodů a spojit je tak, aby vzdálenost mezi nimi byla nejkratší. To je zvláštní případ problému ve studiu.

Greedy algoritmy

Kruskalův algoritmus se odkazuje na "chamtivé" algoritmy (nazývají se také gradientní algoritmy). Podstata těch - největší výhra na každém kroku. Ne vždy "chamtivé" algoritmy poskytují nejlepší řešení úkolu. Existuje teorie, která ukazuje, že při použití na konkrétní problémy poskytují optimální řešení. To je teorie matroidů. Kruskalův algoritmus se týká takových problémů.

Hledání kostry s minimální hmotností

Uvažovaný algoritmus vytváří optimální skelet grafu. Problém o tom je následující. Dan neorientovaný graf bez rovnoběžnými okraji a smyček, a množina hran je dána funkce hmotnost w, která přiřazuje číslo každé hrany e - hmotnost žebro - W (e). Hmotnost každé podmnožiny souboru okrajů je určena součtem závaží okrajů. Je nutné najít kostru s nejmenší hmotností.

Popis

Kruskalův algoritmus funguje takto. Za prvé, všechny hrany původního grafu jsou uspořádány v pořadí podle vzrůstající hmotnosti. Zpočátku rámec neobsahuje žádné hrany, ale zahrnuje všechny vrcholy grafu. Po dalším kroku algoritmu je k již vytvořené části rámce přidán jeden okraj, což je překlenovací les. Není vybráno libovolně. Všechny okraje grafu, které nepatří do kostry, lze nazvat červenou a zelenou. Vrcholy každého červeného žebra jsou v jedné součásti propojenosti lesa a vrcholy zeleně jsou v různých složkách. Pokud tedy do něj přidáte červenou hranu, objeví se cyklus a pokud zelený - ve výsledném lesním kroku bude součást připojení méně o jednu. Proto nemůže být do výsledné konstrukce přidána žádná červená hrana, ale k získání lesa může být přidána jakákoli zelená hrana. A přidá se zelené žebro s minimální hmotností. Výsledkem je kostra s nejmenší hmotností.

Implementace

Označujeme současný les F. Odděluje množinu vrcholů grafu do připojených domén (jejich spojovací formy F a nepřekrývají se ve dvojicích). Červené okraje mají oba vrcholy v jedné části. Část (x) je funkce, která vrací název části, ke které x patří pro každý vrchol x. Spojit (x, y) je postup, který staví nový oddíl sestávající z spojení částí x a y a všech ostatních částí. Nechť n je počet okrajů grafu. Všechny tyto pojmy jsou zahrnuty v algoritmu Kruskal. Implementace:

1. 
   
   
   
   

   Uspořádejte všechny hrany grafu od 1. až po n. Vzestupné hmotnosti. (ai, bi jsou vrcholy hrany s indexem i).

2. pro i = 1 až n.

3. x: = část (ai).

4. y: = část (bi).

5. Pokud x není rovno y, pak Unite (x, y), zahrnout okraj s číslem i v F.

Správnost

Nechť T je kostra původního grafu vytvořeného pomocí Kruskalova algoritmu a nechť S je jeho libovolným skeletem. Je třeba prokázat, že w (T) nepřesahuje w (S).

Nechť M - množinu žeber S, P - množinu žeber T. Jestliže S není rovna T, pak je rámec žebro a T, které nenáleží do S. S. a přiléhají cyklus, se jmenuje C C odebrány ze všech okrajových ES, která patří S. Získá se nový snímek, protože v něm je tolik hran a vrcholů. Jeho váha nepřesahuje w (S), protože w (et) není větší než w (es) algoritmem Kruskal. Tato operace (náhradní žebra T S na žebrech) se opakuje tak dlouho, dokud přijímat T. hmotnost každého následného přijatého rámce není větší než předchozí hmotnosti, což znamená, že w (t) není větší než w (S).

Také správnost Kruskalova algoritmu vyplývá z Rado-Edmondsovy věty o matroidách.

Příklady aplikace algoritmu Kruskal

Dan graf s uzly a, b, c, d, e a žeber (a, b), (a, e), (B, C), (b, e), (c, d), (c, e) , (d, e). Hmotnosti okrajů jsou uvedeny v tabulce a na obrázku. Zpočátku konstrukce lesa F obsahuje všechny vrcholy grafu a neobsahuje jediný okraj. Algoritmus Kruskal nejprve přidat žebro (a, e), protože hmotnost měla nejnižší, a vrcholy A a E jsou v různých složek připojení dřevo F (žebro (a, e) je zelená), pak žebro (c, d), protože že alespoň tato hmotnost hrana grafu hran, které nepatří do F, a to je zelená, pak ze stejných důvodů připadají okraje (a, b). Ale okraj (b, e) se vede, i když a minimální hmotnost zbývajících hran, protože to je červená: vrcholy b a e patří do stejné složky lesních připojení F, to znamená, že pokud k tomu přidáme F okraj (b, e), je vytvořen cyklus. Potom se přidá zelený okraj (B, C), je předán červenou hranu (C, E), a pak D, E. Tak, hrany jsou přidány (a, e), (c, d), (a, b), (b, c). Z toho je optimální kostra původního grafu. Takto funguje algoritmus Crascal v tomto případě. Příklad ukazuje toto.

Na obrázku je graf sestávající ze dvou komponent konektivity. Tučné čáry ukazují okraje optimálního rámce (zeleně), které byly vytvořeny pomocí algoritmu Kruskal.

Horní obrázek zobrazuje původní graf a na dolním obrázku - kostru minimální hmotnosti, která byla pro ni konstruována pomocí uvažovaného algoritmu.

Sekvence z přidaných žeber (1,6) - (0,3), (2,6) nebo (2,6), (0,3) - není has- (3.4) - (0,1) (1.6) nebo (1.6), (0.1) je také lhostejná (5.6).

Kruskalův algoritmus najde praktickou aplikaci například pro optimalizaci komunikačních podložek, silnic v nových čtvrtích v lokalitách každé země a také v jiných případech.