Kruskalův algoritmus - stavba optimálního rámce

V časném geometrem 19. století Jakob Steiner z Berlína za úkol o tom, jak se připojit tři vesnice, aby jejich délka byla co nejkratší. Později shrnul problém: je nutné nalézt bod v rovině, vzdálenost od něj, aby n jiných místech byly nejnižší. V 20. století, pokračuje v práci na tomto tématu. Bylo rozhodnuto, že trvat několik bodů a spojit je takovým způsobem, aby vzdálenost mezi nimi byla co nejkratší. To vše je zvláštní příklad problému být studován.

„Chamtivý“ algoritmus

Kruskalův algoritmus odkazuje na „chamtivý“ algoritmu (také nazývaný gradient). Podstatou těch - nejvyšší výhra na každém kroku. Ne vždy, „hladové“ algoritmy poskytují nejlepší řešení tohoto problému. Existuje teorie, což ukazuje, že při jejich aplikaci na konkrétní úkoly, které dávají optimální řešení. To je teorie matroidů. Kruskalův algoritmus vztahuje k takovým problémům.

Nalezení minimální hmotnost kostry

Zobrazení algoritmus konstrukce optimální počet rámců. Problém to 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ého podsouboru většího počtu žeber je součet hmotností svého okraje. Požadováno, aby nalezli kostru malou hmotností.

popis

Kruskalův algoritmus funguje. Za prvé, všechny hrany počáteční grafu jsou uspořádány ve vzestupném pořadí závaží. Zpočátku, rám neobsahuje žádné žebra, ale zahrnuje všechny vrcholy. Po dalším kroku algoritmu do již vybudované části kostry, která je překlenutí les, přidá se jeden okraj. Není vybrány libovolně. Všechny hrany grafu, které nepatří k rámu, lze označit červeně a zeleně. V horní části každé červené okraje jsou ve stejné složce pod konektivitou konstrukce lesní a zelené vrcholy - různé. Proto, pokud přidáte k červené hranici, tam je cyklus, a v případě, že zelená - jako doručené po tomto kroku dřevěné připojená zařízení bude méně než jedna. To znamená, že výsledná stavba nelze přidat žádnou červenou hranu, ale každý zelený okraj mohou být přidány do dostat do lesa. A dodává zelenou hranou s minimální hmotností. Výsledkem je rámec minimální hmotnosti.

uskutečnění

Označují aktuální les F. To rozděluje řadu vrcholů v oblasti konektivity (jejich odboroví formy F a jsou disjunktní). Na obou stranách červených vrcholů, které leží v jednom kuse. Část (x) - funkce, která pro každý vrchol x vrací část jména, patří x. Unite (x, y) - postup, který vytvoří nový oddíl, který se skládá z kombinací částí X a Y a všechny ostatní díly. Nechť n - počet hran. Všechny tyto pojmy jsou zahrnuty v kruskalův algoritmus. realizace:

1. Uspořádat všechny hrany grafu od 1. do n-tého vzestupných závaží. (Ai, bi - i s vrcholovým počtem hran).

2. pro i = 1 až n dělat.

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

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

5. Pokud x není rovno y potom Unite (x, y) tak, aby zahrnoval s počtem hran F i.

korektnost

Nechť T - rám původního grafu konstruovány s použitím algoritmu Kruskal a S - jeho libovolný rám. Musíme dokázat, že w (T) není větší než 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áme nového rámu, protože hrany a vrcholy je stejný. Jeho hmotnost není větší než w (S), protože w (ET) v napájecím Kruskal algoritmu již w (y). 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).

Robustnost kruskalův algoritmus Z teorému Rado-Edmonds na matroidy.

Příklady použití Kruskal algoritmus

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 hran jsou uvedeny v tabulce a na obrázku. Zpočátku, výstavba lesních F obsahuje všechny vrcholy grafu a neobsahuje žádná žebra. 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 nihera optimální rámu a sestává z původního grafu. Takže v tomto případě funguje algoritmus Kruskal. Příklad je zobrazen.

Na obrázku je znázorněn graf, který se skládá ze dvou spojených komponent. Tučně čáry označují optimální žebra rám (zelená), zkonstruované pomocí algoritmu Kruskal.

Horní obrázek ukazuje původní graf a dno - kostru minimální hmotnosti, postavený pro něj pomocí algoritmu.

Sekvence z přidaných žeber (1,6); (0,3), (2,6) nebo (2,6), (0,3) - není důležité; (3,4); (0,1), (1,6) nebo (1,6), (0,1), také péče (5,6).

Kruskalův algoritmus nalezne praktické uplatnění, například pro optimalizaci těsnění komunikace, silnice v nových sídlišť míst v každé zemi, stejně jako v ostatních případech.