Minimální kostra - Minimum spanning tree - Wikipedia

A rovinný graf a jeho minimální kostra. Každá hrana je označena svou hmotností, která je zde zhruba úměrná její délce.

A minimální kostra (MST) nebo minimální hmotnost překlenující strom je podmnožina okrajů a připojeno, hranově vážený neorientovaný graf, který spojuje všechny vrcholy společně, bez jakýchkoli cykly a s minimální možnou celkovou hmotností hran. To znamená, že je kostra jehož součet okrajových hmotností je co nejmenší. Obecněji řečeno, jakýkoli hranově vážený neorientovaný graf (nemusí být nutně spojen) má a minimální les, což je spojení minimálních klenutých stromů pro jeho připojené komponenty.

Existuje poměrně málo případů použití pro minimální kostry. Jedním příkladem by mohla být telekomunikační společnost, která by se pokusila položit kabel do nové čtvrti. Pokud je omezeno zakopat kabel pouze po určitých cestách (např. Silnicích), pak by existoval graf obsahující body (např. Domy) spojené těmito cestami. Některé cesty mohou být dražší, protože jsou delší nebo vyžadují hlubší zakopání kabelu; tyto cesty by byly reprezentovány hranami s větší váhou. Měna je přijatelnou jednotkou pro hmotnost hran - neexistuje požadavek, aby se délky hran řídily běžnými pravidly geometrie, jako je nerovnost trojúhelníku. A kostra protože ten graf by byl podmnožinou těch cest, které nemají žádné cykly, ale přesto spojují každý dům; může existovat několik možných koster. A minimální kostra by byl ten s nejnižšími celkovými náklady, představující nejméně nákladnou cestu pro pokládku kabelu.

Vlastnosti

Možná multiplicita

Pokud existují n vrcholy v grafu, pak má každý kostra n − 1 hrany.

Tento obrázek ukazuje, že v grafu může být více než jeden minimální kostra. Na obrázku jsou dva stromy pod grafem dvě možnosti minimální kostry daného grafu.

Může existovat několik minimálně rostoucích stromů stejné hmotnosti; zejména pokud jsou všechny okrajové váhy daného grafu stejné, pak je každý spanningový strom daného grafu minimální.

Jedinečnost

Pokud má každá hrana odlišnou váhu, bude existovat pouze jeden, jedinečný minimální kostra. To platí v mnoha realistických situacích, jako je příklad telekomunikační společnosti výše, kde je nepravděpodobné, že by existovaly dvě cesty přesně stejné náklady. To zobecňuje i na lesy.

Důkaz:

1. Předpokládejme opak, že existují dva různé MST A a B.
2. Od té doby A a B se liší, přestože obsahuje stejné uzly, existuje alespoň jedna hrana, která patří jednomu, ale ne druhému. Mezi takovými okraji nechte E₁ být ten s nejnižší hmotností; tato volba je jedinečná, protože okrajové váhy jsou odlišné. Bez ztráty všeobecnosti, předpokládejme E₁ je v A.
3. Tak jako B je MST, {E₁} ${ displaystyle cup}$ B musí obsahovat cyklus C s E₁.
4. Jako strom, A neobsahuje žádné cykly C musí mít výhodu E₂ to není v A.
5. Od té doby E₁ byl vybrán jako jedinečný okraj s nejnižší hmotností mezi těmi, které patří přesně jednomu z A a B, váha E₂ musí být větší než hmotnost E₁.
6. Tak jako E₁ a E₂ jsou součástí cyklu C, nahrazují E₂ s E₁ v B proto dává kostru s menší váhou.
7. To je v rozporu s předpokladem B je MST.

Obecněji řečeno, pokud okrajové váhy nejsou všechny odlišné, pak je jedinečná pouze (multi-) sada závaží v minimálních rozpětích stromů; je to stejné pro všechny minimální stromy.^[1]

Podgraf s minimálními náklady

Pokud jsou závaží pozitivní, pak je minimální kostra ve skutečnosti minimální cenou podgraf spojující všechny vrcholy, protože podgrafy obsahují cykly nutně mít větší celkovou hmotnost.^{[Citace je zapotřebí ]}

Vlastnost cyklu

Pro jakýkoli cyklus C v grafu, pokud je váha hrany E z C je větší než jednotlivé váhy všech ostatních okrajů C, pak tato hrana nemůže patřit k MST.

Důkaz: Předpokládejme opak, tj. to E patří k MST T₁. Poté mazání E zlomí se T₁ do dvou podstromů se dvěma konci E v různých podstromech. Zbývající část C znovu připojí podstromy, proto je zde hrana F z C s konci v různých podstromech, tj. znovu připojí podstromy ke stromu T₂ s hmotností menší než T₁, protože váha F je menší než hmotnost E.

Vyjmout vlastnost

Tento obrázek ukazuje vlastnost cut MST. T je jediný MST daného grafu. Pokud S = {A, B, D, E}, tedy VS = {C, F}, pak existují 3 možnosti hrany přes řez (S, VS), jsou to hrany BC, EC, EF originálu graf. Potom je e jedním z okrajů minimální hmotnosti pro řez, proto je S ∪ {e} součástí MST T.

Pro všechny střih C grafu, pokud je váha hrany E v řezané sadě C je přísně menší než hmotnost všech ostatních okrajů řezané sady C, pak tato hrana patří všem MST grafu.

Důkaz: Převzít že existuje MST T který neobsahuje E. Přidávání E na T vytvoří cyklus, který jednou prochází řezem E a přejde zpět na další hranu E' . Mazání E' dostaneme klenutý strom T ∖ {e '} ∪ {e} přísně menší hmotnosti než T. To je v rozporu s předpokladem T byl MST.

Podobným argumentem, pokud má více než jedna hrana minimální hmotnost napříč řezem, pak je každá taková hrana obsažena v nějakém minimálním rozpětí stromu.

Okraj s minimálními náklady

Pokud jsou minimální náklady na hranici E grafu je jedinečný, pak je tato hrana zahrnuta v libovolném MST.

Důkaz: pokud E nebyl zahrnut do MST, odstranění kteréhokoli z (větších nákladů) okrajů v cyklu vytvořeném po přidání E k MST, by přineslo klenutý strom menší váhy.

Kontrakce

Pokud T je strom hran MST, pak můžeme smlouva T do jediného vrcholu při zachování invariantu, že MST kontraktovaného grafu plus T dává MST pro graf před kontrakcí.^[2]

Algoritmy

Ve všech níže uvedených algoritmech m je počet hran v grafu a n je počet vrcholů.

Klasické algoritmy

První algoritmus pro nalezení minimálního kostry byl vyvinut českým vědcem Otakar Borůvka v roce 1926 (viz Borůvkův algoritmus ). Jeho účelem bylo efektivní elektrické pokrytí Morava. Algoritmus probíhá v posloupnosti fází. V každé fázi tzv Boruvka krok, identifikuje les F skládající se z hrany minimální váhy dopadající na každý vrchol v grafu G, poté vytvoří graf ${ displaystyle G_ {1} = G setminus F}$ jako vstup do dalšího kroku. Tady ${ displaystyle G setminus F}$ označuje graf odvozený z G smršťováním hran v F (podle Vyjmout vlastnost, tyto hrany patří k MST). Každý krok Boruvky trvá lineárně. Protože počet vrcholů je v každém kroku snížen alespoň o polovinu, Boruvkův algoritmus bere O (m log n) čas.^[2]

Druhý algoritmus je Primův algoritmus, který vynalezl Vojtěch Jarník v roce 1930 a znovu objeven Prim v roce 1957 a Dijkstra v roce 1959. V zásadě roste MST (T) po jedné hraně. Zpočátku, T obsahuje libovolný vrchol. V každém kroku T je doplněn okrajem s nejnižší hmotností (X,y) takové, že X je v T a y ještě není v T. Podle Vyjmout vlastnost, všechny hrany přidány do T jsou v MST. Jeho běh je buď O (m log n) nebo O (m + n log n), v závislosti na použitých datových strukturách.

Třetí běžně používaný algoritmus je Kruskalův algoritmus, který také bere O (m log n) čas.

Čtvrtý algoritmus, který se běžně nepoužívá, je algoritmus zpětného mazání, což je opak Kruskalova algoritmu. Jeho runtime je O (m log n (log log n)³).

Všichni čtyři jsou chamtivé algoritmy. Protože běží v polynomiálním čase, je problém najít takové stromy FPa související rozhodovací problémy například stanovení, zda je konkrétní hrana v MST, nebo určení, zda minimální celková hmotnost přesahuje určitou hodnotu, jsou v P.

Rychlejší algoritmy

Několik vědců se pokusilo najít výpočetně efektivnější algoritmy.

V srovnávacím modelu, ve kterém jsou jedinými povolenými operacemi na hranových vahách párová srovnání, Karger, Klein & Tarjan (1995) najít lineární časově randomizovaný algoritmus založené na kombinaci Borůvkova algoritmu a algoritmu reverzního mazání.^[3][4]

Nejrychlejší nerandomizovaný algoritmus založený na srovnání se známou složitostí Bernard Chazelle, je založen na měkká hromada, přibližná prioritní fronta.^[5][6] Jeho doba provozu je Ó (m α (m,n)), kde α je klasický funkční inverzní funkce Ackermann. Funkce α roste extrémně pomalu, takže pro všechny praktické účely ji lze považovat za konstantu ne větší než 4; Chazelův algoritmus tedy trvá velmi blízko lineárnímu času.

Algoritmy lineárního času ve zvláštních případech

Husté grafy

Pokud je graf hustý (tj. m/n ≥ log log log n), pak deterministický algoritmus Fredmana a Tarjana najde MST v čase O (m).^[7] Algoritmus provádí řadu fází. Každá fáze se provede Primův algoritmus mnohokrát, každý na omezený počet kroků. Délka každé fáze je O (m+n). Pokud je počet vrcholů před fází ${ displaystyle n '}$, počet vrcholů zbývajících po fázi je maximálně ${ displaystyle n '/ 2 ^ {m / n'}}$. Proto nanejvýš ${ displaystyle log ^ {*} {n}}$ fáze jsou potřebné, což poskytuje lineární běh pro husté grafy.^[2]

Existují i ​​další algoritmy, které pracují v lineárním čase na hustých grafech.^[5][8]

Celočíselné váhy

Pokud jsou hranové váhy celá čísla reprezentovaná v binárním formátu, jsou známy deterministické algoritmy, které řeší problém v Ó(m + n) celočíselné operace.^[9]Zda lze problém vyřešit deterministicky pro obecný graf v lineární čas algoritmem založeným na srovnání zůstává otevřenou otázkou.

Rozhodovací stromy

Daný graf G kde jsou uzly a hrany pevné, ale váhy nejsou známy, je možné sestrojit binární soubor rozhodovací strom (DT) pro výpočet MST pro jakoukoli permutaci vah. Každý vnitřní uzel DT obsahuje srovnání mezi dvěma hranami, např. „Je váha hrany mezi X a y větší než hmotnost hrany mezi w a z? ". Dvě děti uzlu odpovídají dvěma možným odpovědím" ano "nebo" ne ". V každém listu DT je ​​seznam hran od G které odpovídají MST. Runtime složitost DT je ​​největší počet dotazů potřebných k nalezení MST, což je jen hloubka DT. DT pro graf G je nazýván optimální pokud má nejmenší hloubku ze všech správných DT pro G.

Pro každé celé číslo r, je možné najít optimální rozhodovací stromy pro všechny grafy r vrcholy o vyhledávání hrubou silou. Toto hledání probíhá ve dvou krocích.

A. Generování všech potenciálních DT

• Existují ${ displaystyle 2 ^ {r vyberte 2}}$ různé grafy na r vrcholy.
• Pro každý graf lze MST vždy najít pomocí r(r-1) srovnání, např. podle Primův algoritmus.
• Proto je hloubka optimálního DT menší než ${ displaystyle r ^ {2}}$.
• Proto je počet vnitřních uzlů v optimálním DT menší než ${ displaystyle 2 ^ {r ^ {2}}}$.
• Každý vnitřní uzel porovnává dvě hrany. Počet hran je maximálně ${ displaystyle r ^ {2}}$ rozdílný počet srovnání je tedy nanejvýš ${ displaystyle r ^ {4}}$.
• Počet potenciálních DT je ​​tedy menší než: ${ displaystyle {(r ^ {4})} ^ {(2 ^ {r ^ {2}})} = r ^ {2 ^ {(r ^ {2} +2)}}}$.

B. Identifikace správných DTChcete-li zkontrolovat, zda je DT správný, měl by být zkontrolován na všech možných permutacích okrajových závaží.

• Počet takových permutací je maximálně ${ displaystyle (r ^ {2})!}$.
• Pro každou permutaci vyřešte problém MST na daném grafu pomocí jakéhokoli existujícího algoritmu a porovnejte výsledek s odpovědí danou DT.
• Doba chodu jakéhokoli algoritmu MST je maximálně ${ displaystyle (r ^ {2})}$, takže celková doba potřebná ke kontrole všech permutací je maximálně ${ displaystyle (r ^ {2} +1)!}$.

Celková doba potřebná k nalezení optimálního DT pro Všechno grafy s r vrcholy je: ${ displaystyle 2 ^ {r vyberte 2} cdot r ^ {2 ^ {(r ^ {2} +2)}} cdot (r ^ {2} +1)!}$, což je méně než: ${ displaystyle 2 ^ {2 ^ {r ^ {2} + o (r)}}}$.^[2]

Optimální algoritmus

Seth Pettie a Vijaya Ramachandran našli prokazatelně optimální deterministický srovnávací algoritmus minimálního rozprostírajícího se stromu.^[2] Následuje zjednodušený popis algoritmu.

1. Nechat ${ displaystyle r = log log log n}$, kde n je počet vrcholů. Najděte všechny optimální rozhodovací stromy r vrcholy. To lze provést v čase O (n) (viz Rozhodovací stromy výše).
2. Rozdělte graf na součásti maximálně r vrcholy v každé složce. Tento oddíl používá a měkká hromada, který „poškodí“ malý počet okrajů grafu.
3. Použijte optimální rozhodovací stromy k vyhledání MST pro nepoškozený podgraf v rámci každé komponenty.
4. Kontraktujte každou připojenou komponentu rozloženou MST na jeden vrchol a použijte jakýkoli algoritmus, na kterém funguje husté grafy v čase O (m) ke kontrakci nepoškozeného podgrafu
5. Přidejte poškozené hrany do výsledné doménové struktury a vytvořte podgraf, který bude zaručeně obsahovat minimální kostru a bude menší o konstantní faktor než počáteční graf. Optimální algoritmus použijte rekurzivně na tento graf.

Runtime všech kroků v algoritmu je O (m), kromě kroku použití rozhodovacích stromů. Runtime tohoto kroku není znám, ale bylo prokázáno, že je optimální - žádný algoritmus nedokáže lépe než optimální rozhodovací strom. Tento algoritmus má tedy zvláštní vlastnost, kterou je prokazatelně optimální i když jeho běhová složitost je neznámý.

Paralelní a distribuované algoritmy

Výzkum také zvažoval paralelní algoritmy pro problém s minimálním kostrou. S lineárním počtem procesorů je možné problém vyřešit v ${ displaystyle O ( log n)}$ čas.^[10][11]Bader & Cong (2006) předvést algoritmus, který dokáže vypočítat MST 5krát rychleji na 8 procesorech než optimalizovaný sekvenční algoritmus.^[12]

Byly navrženy další specializované algoritmy pro výpočet minimálních rozpětí stromů grafu tak velkých, že většina z nich musí být vždy uložena na disku. Tyto externí úložiště algoritmy, například jak je popsáno v „Engineering an External Memory Minimum Spanning Tree Algorithm“ od Romana, Dementiev et al.,^[13] může pracovat, podle tvrzení autorů, jen 2 až 5krát pomaleji než tradiční algoritmus v paměti. Spoléhají na efektivní algoritmy třídění externího úložiště a dál kontrakce grafu techniky pro efektivní zmenšení velikosti grafu.

K problému lze přistupovat také v a distribuovaným způsobem. Pokud je každý uzel považován za počítač a žádný uzel neví nic kromě svých vlastních připojených odkazů, lze stále vypočítat distribuovaný minimální kostra.

MST na kompletních grafech

Alan M. Frieze ukázal, že vzhledem k kompletní graf na n vrcholy, s hranovými váhami, které jsou nezávislé identicky distribuované náhodné proměnné s distribuční funkcí ${ displaystyle F}$ uspokojující ${ displaystyle F '(0)> 0}$, pak jako n přístupy +∞ očekávaná váha MST se blíží ${ displaystyle zeta (3) / F '(0)}$, kde ${ displaystyle zeta}$ je Funkce Riemann zeta (konkrétněji je ${ displaystyle zeta (3)}$ Apéryho konstanta ). Vlys a Steele také prokázal konvergenci v pravděpodobnosti. Svante Janson prokázal teorém centrálního limitu pro hmotnost MST.

Pro jednotné náhodné váhy v ${ displaystyle [0,1]}$, byla pro malé úplné grafy vypočítána přesná očekávaná velikost minimálního kostry.^[14]

Aplikace

Minimum spanning trees have direct applications in the design of networks, including počítačové sítě, telekomunikační sítě, dopravní sítě, vodovodní sítě, a elektrické sítě (pro které byly poprvé vynalezeny, jak bylo uvedeno výše).^[15] Jsou vyvolávány jako podprogramy v algoritmech pro další problémy, včetně Christofidův algoritmus pro přiblížení problém obchodního cestujícího,^[16] aproximace problému minimálního výřezu na více terminálech (což je v případě jednoho terminálu ekvivalentní problému problém s maximálním průtokem ),^[17]a přiblížení minimálních nákladů vážené dokonalé vhodný.^[18]

Mezi další praktické aplikace založené na minimálních rozpětích stromů patří:

• Taxonomie.^[19]
• Shluková analýza: shlukovací body v rovině,^[20] shlukování s jedním spojením (metoda hierarchické shlukování ),^[21] graficko-teoretické shlukování,^[22] a shlukování genová exprese data.^[23]
• Stavba stromů pro vysílání v počítačových sítích.^[24]
• Registrace obrázku^[25] a segmentace^[26] - viz minimální segmentace založená na stromech.
• Křivočaré extrakce funkcí v počítačové vidění.^[27]
• Rozpoznávání rukopisu matematických výrazů.^[28]
• Návrh obvodu: implementace efektivních vícenásobných konstantních násobení, jak se používají v konečná impulzní odezva filtry.^[29]
• Regionalizace sociogeografických oblastí, seskupení oblastí do homogenních souvislých regionů.^[30]
• Porovnávání ekotoxikologie data.^[31]
• Topologické pozorovatelnost v energetických systémech.^[32]
• Měření homogenity dvojrozměrných materiálů.^[33]
• Minimax kontrola procesu.^[34]
• K popisu finančních trhů lze také použít minimální kostry.^[35][36] Korelační matici lze vytvořit výpočtem korelačního koeficientu mezi libovolnými dvěma stavy. Tuto matici lze topologicky reprezentovat jako složitou síť a pro vizualizaci vztahů lze zkonstruovat minimální kostru.

Související problémy

Minimální Steinerovy stromy vrcholů pravidelných mnohoúhelníků s N = 3 až 8 stran. Nejnižší délka sítě L pro N > 5 je obvod menší než jedna strana. Čtverce představují Steinerovy body.

Problém najít Steinerův strom podmnožiny vrcholů, tj. minimálního stromu, který překlenuje danou podmnožinu, je známo NP-Complete.^[37]

Souvisejícím problémem je k-minimální kostra (k-MST), což je strom, který pokrývá určitou podmnožinu k vrcholy v grafu s minimální hmotností.

Sada k-nejmenší kostry je podmnožinou k spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight.^[38][39][40] (Upozorňujeme, že tento problém nesouvisí s k- minimální kostra.)

The Euklidovský minimální kostra je kostra grafu s hranovými váhami odpovídajícími euklidovské vzdálenosti mezi vrcholy, což jsou body v rovině (nebo prostoru).

The přímočarý minimální kostra je kostra grafu s hranovými váhami odpovídajícími přímá vzdálenost mezi vrcholy, které jsou body v rovině (nebo prostoru).

V distribuovaný model, kde je každý uzel považován za počítač a žádný uzel neví nic kromě vlastních propojených odkazů, lze uvažovat distribuovaný minimální kostra. Matematická definice problému je stejná, ale existují různé přístupy k řešení.

The kapacitní minimální kostra je strom, který má označený uzel (počátek nebo kořen) a každý z podstromů připojených k uzlu neobsahuje více než C uzly. C se nazývá kapacita stromu. Optimální řešení CMST je NP-tvrdé,^[41] ale dobrá heuristika, jako je Esau-Williams a Sharma, vytváří řešení blízká optimálnímu v polynomiálním čase.

The stupeň omezený minimální kostra je minimální kostra, ve které je každý vrchol spojen s maximálně d jiné vrcholy, pro některé dané číslo d. Pouzdro d = 2 je speciální případ problém obchodního cestujícího, takže minimální omezený strom je omezený stupněm NP-tvrdé obecně.

Pro řízené grafy, problém s minimálním kostrou se nazývá Arborescence problém a lze jej vyřešit v kvadratickém čase pomocí Algoritmus Chu – Liu / Edmonds.

A maximální kostra je překlenovací strom s váhou větší nebo rovnou hmotnosti každého dalšího překlenovacího stromu. Takový strom lze najít pomocí algoritmů, jako je Prim's nebo Kruskal's, po vynásobení hranových vah číslem -1 a vyřešení problému MST v novém grafu. Cesta v maximálním kostře je nejširší cesta v grafu mezi jeho dvěma koncovými body: mezi všemi možnými cestami maximalizuje váhu hrany minimální váhy.^[42]Maximum spanning trees find applications in analýza algoritmy pro přirozené jazyky^[43]a ve výcvikových algoritmech pro podmíněná náhodná pole.

The dynamický MST problém se týká aktualizace dříve vypočítaného MST po změně hmotnosti hrany v původním grafu nebo vložení / odstranění vrcholu.^[44][45][46]

Problémem minimálního značení překlenovacího stromu je najít překlenovací strom s nejmenšími typy štítků, pokud je každá hrana v grafu spojena se štítkem z konečné sady štítků místo váhy.^[47]

Hrana úzkého hrdla je nejvyšší vážená hrana v kostře. Spanning tree je a minimální překlenutí překlenující strom (nebo MBST) pokud graf neobsahuje spanning tree s menší váhou hrany úzkého hrdla. MST je nutně MBST (prokazatelný vlastnost cut ), ale MBST nemusí být nutně MST.^[48][49]

Reference

Další čtení

• Otakar Boruvka o problému Minimum Spanning Tree Problem (překlad obou článků z roku 1926, komentáře, historie) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Část 7 uvádí jeho algoritmus, který vypadá jako křížení mezi Primovým a Kruskalovým.)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7. Kapitola 23: Minimum Spanning Trees, str. 561–579.
• Eisner, Jason (1997). Nejmodernější algoritmy pro minimální kostry: Diskuse o cvičení. Rukopis, University of Pennsylvania, duben. 78 stran
• Kromkowski, John David. „Po všech těch letech stále nerozpustný“, v Annual Editions, Race and Ethnic Relations, 17 / e (2009 McGraw Hill) (Využití minimálního stromu jako metody demografické analýzy etnické rozmanitosti ve Spojených státech).

externí odkazy

• Implementováno v BGL, knihovně Boost Graph
• Úložiště algoritmu Stony Brook - kódy minimálního rozpětí stromu
• Implementováno v QuickGraph pro .Net