Spanning tree - Spanning tree

Překlenující strom (modré těžké hrany) mřížkového grafu

V matematickém oblasti teorie grafů , je kostra T z undirected grafu G je subgraph že je strom , který obsahuje všechny vrcholy v G . Obecně může mít graf několik koster, ale graf, který není připojen , nebude obsahovat kostru (viz kostry níže). Pokud jsou všechny hrany z G jsou rovněž okrajů kostry T o G , pak G je strom, a je identická s T (to znamená, že strom má jedinečnou kostru a je sama).

Aplikace

Několik algoritmů pro hledání cest , včetně Dijkstrova algoritmu a vyhledávacího algoritmu A * , interně vytváří překlenovací strom jako mezistupeň při řešení problému.

Aby se minimalizovaly náklady na energetické sítě, kabelové připojení, potrubí, automatické rozpoznávání řeči atd., Lidé často používají algoritmy, které postupně vytvářejí spanning tree (nebo mnoho takových stromů) jako mezikroky v procesu hledání minimálního spanning stromu .

Internet a mnoho dalších telekomunikačních sítí mají přenosová spojení, která spojují uzly dohromady v síťové topologii, která zahrnuje některé smyčky. Aby se zabránilo přemosťovacím smyčkám a směrovacím smyčkám , mnoho směrovacích protokolů určených pro takové sítě - včetně protokolu Spanning Tree Protocol , Open Shortest Path First , Link-state routing protocol , Augmented tree-based routing atd. - vyžaduje, aby si každý router pamatoval kostra.

V topologické teorii grafů se k nalezení vložení grafů s maximálním rodem používá zvláštní druh kostry, strom Xuong . Strom Xuong je překlenovací strom, takže ve zbývajícím grafu je počet připojených komponent s lichým počtem hran co nejmenší. Strom Xuong a související vložení maximálního rodu lze nalézt v polynomiálním čase .

Definice

Strom je připojený neorientovaný graf bez cyklů . Jedná se o překlenující strom grafu G, pokud překlenuje G (to znamená, že zahrnuje každý vrchol G ) a je podgrafem G (každá hrana ve stromu patří G ). Rozpínací strom připojeného grafu G lze také definovat jako maximální sadu hran G, která neobsahuje žádný cyklus, nebo jako minimální sadu hran, které spojují všechny vrcholy.

Základní cykly

Přidáním pouze jedné hrany do kostry vytvoříte cyklus; takový cyklus se nazývá základní cyklus . Pro každou hranu, která není v kostře, existuje zřetelný základní cyklus; existuje tedy vzájemná korespondence mezi základními cykly a hranami, které nejsou v kostře. Pro připojený graf s vrcholy V bude mít jakýkoli spanningový strom  hrany V - 1, a tedy graf hran E a jeden z jeho spanning stromů bude mít  základní cykly E  -  V + 1 (počet hran odečtený od počtu hrany zahrnuty v kostře; udávající počet hran, které nejsou zahrnuty v kostře). Pro jakýkoli daný spanningový strom tvoří sada všech  základních cyklů E  -  V + 1 základ cyklu , základ pro prostor cyklu .

Základní sady

Duální pojetí základního cyklu je pojetí základní sady . Odstraněním pouze jedné hrany rozloženého stromu se vrcholy rozdělí na dvě nesouvislé sady. Základní sada je definována jako sada hran, které musí být odstraněny z grafu G, aby se dosáhlo stejného oddílu. Každý kostra tedy definuje sadu  základních sad V - 1, jednu pro každou hranu kostry.

Dualita mezi základními sadami a základními cykly se stanoví konstatováním, že hrany cyklu, které nejsou ve stromu, se mohou objevit pouze v sadách ostatních hran v cyklu; a naopak : hrany v řezu se mohou objevit pouze v těch cyklech, které obsahují hranu odpovídající řezu. Tuto dualitu lze také vyjádřit pomocí teorie matroidů , podle které je spanning tree základem grafického matroidu , fundamentálním cyklem je jedinečný okruh v sadě vytvořený přidáním jednoho prvku k základně a jsou definovány základní cutets stejným způsobem z duálního matroidu .

Rozkládající se lesy

V grafech, které nejsou připojeny, nemůže existovat žádný překlenovací strom a místo toho je třeba zvážit překlenutí lesů . Zde existují dvě konkurenční definice:

• Někteří autoři považují spanning forest za maximální acyklický podgraf daného grafu, nebo ekvivalentně za graf sestávající z spanningového stromu v každé připojené komponentě grafu.
• Pro ostatní autory je překlenovací les les, který pokrývá všechny vrcholy, což znamená, že každý vrchol grafu je vrcholem v lese. U této definice může mít i připojený graf odpojený les, například les, ve kterém každý vrchol tvoří strom s jedním vrcholem.

Aby nedocházelo k záměně mezi těmito dvěma definicemi, Gross & Yellen (2005) navrhují termín „les plný lesů“ pro les lesů se stejnou konektivitou jako daný graf, zatímco Bondy & Murty (2008) místo toho tento les nazývají „ "maximální les".

Počítám kostry

Cayleyův vzorec spočítá počet koster na úplném grafu. Jsou tam stromy , stromy a stromy .${\ displaystyle 2 ^ {2-2} = 1}$${\ displaystyle K_ {2}}$${\ displaystyle 3 ^ {3-2} = 3}$${\ displaystyle K_ {3}}$${\ displaystyle 4 ^ {4-2} = 16}$${\ displaystyle K_ {4}}$

Počet t ( G ) stromů spojeného grafu je dobře prostudovaný invariant .

V konkrétních grafech

V některých případech je snadné vypočítat t ( G ) přímo:

• Pokud G je sám o sobě strom, pak t ( G ) = 1 .
• Když G je cyklický graf C _n s n vrcholy, pak t ( G ) =  n .
• Pro kompletní graf s n vrcholy dává Cayleyův vzorec počet stromů jako n ^{n  - 2} .
• Pokud G je úplný bipartitní graf , pak .${\ displaystyle K_ {p, q}}$${\ displaystyle t (G) = p ^ {q-1} q ^ {p-1}}$
• U n -dimenzionálního hyperkrychlového grafu je počet spanning trees .${\ displaystyle Q_ {n}}$${\ displaystyle t (G) = 2 ^ {2 ^ {n} -n-1} \ prod _ {k = 2} ^ {n} k ^ {n \ zvolit k}}$

V libovolných grafech

Obecněji řečeno, pro jakýkoli grafu G , počet t ( G ) se může vypočítat v polynomiálním čase jako determinant části matrice odvozené z grafu, pomocí Kirchhoffova matrice strom věta .

Konkrétně, pro výpočet t ( G ), jeden konstruuje Laplacian matice grafu, čtvercová matice, ve které řádky a sloupce jsou oba indexovány vrcholů G . Položka v řádku i a sloupci j je jednou ze tří hodnot:

• Stupeň vrcholu i , pokud i  =  j ,
• −1, pokud vrcholy i a j sousedí, nebo
• 0, pokud se vrcholy i a j navzájem liší, ale nesousedí.

Výsledná matice je singulární , takže její determinant je nula. Odstranění řádku a sloupce pro libovolně zvolený vrchol však vede k menší matici, jejíž determinant je přesně  t ( G ).

Smazání-kontrakce

Pokud G je graf nebo multigraf a e je libovolná hrana G , pak počet t ( G ) spanningových stromů G uspokojí opakování deleční-kontrakce t ( G ) =  t ( G  -  e ) +  t ( G / e ), kde G  -  e je multigraf získaný odstraněním e a G / e je kontrakce z G o e . Termín t ( G  -  e ) v tomto vzorci počítá spanning stromy  G , které nepoužívají hranu  e , a termín t ( G / e ) počítá spanning stromy  G, které používají  e .

V tomto vzorci v případě, že daný graf G je multigraf , nebo v případě, že kontrakce způsobí dva vrcholy, které mají být připojeny k sobě navzájem pomocí několika hranami, pak nadbytečné hrany nesmí být odstraněna, protože to by vedlo k nesprávným celkem. Například vazební graf spojující dva vrcholy k hranami má k různé kostry, z nichž každý sestává z jednoho z těchto okrajů.

Tutteův polynom

Tutte polynom grafu lze definovat jako suma, nad kostry grafu, pojmů vypočtených z „vnitřní aktivity“ a „vnější“ aktivita stromu. Jeho hodnota v argumentech (1,1) je počet kosterních stromů nebo v odpojeném grafu počet maximálních kosterních lesů.

Polynom Tutte lze také vypočítat pomocí opakování delece-kontrakce, ale jeho výpočetní složitost je vysoká: pro mnoho hodnot jeho argumentů je jeho výpočet přesně # P-úplný a je také těžké jej aproximovat se zaručeným poměrem přiblížení . Bod (1,1), ve kterém jej lze vyhodnotit pomocí Kirchhoffovy věty, je jednou z mála výjimek.

Algoritmy

Konstrukce

Jediný překlenovací strom grafu lze najít v lineárním čase buď prohledáním do hloubky, nebo do šířky . Oba tyto algoritmy zkoumají daný graf, počínaje libovolným vrcholem v , procházením sousedů vrcholů, které objevují, a přidáním každého neprozkoumaného souseda k datové struktuře, která bude později prozkoumána. Liší se v tom, zda je tato datová struktura zásobníkem (v případě hloubkového vyhledávání) nebo frontou (v případě vyhledávání na šířku). V obou případech lze vytvořit spanningový strom připojením každého vrcholu kromě kořenového vrcholu v k vrcholu, ze kterého byl objeven. Tento strom je známý jako hloubkový první vyhledávací strom nebo jako první vyhledávací strom podle algoritmu průzkumu grafů použitého k jeho vytvoření. Stromy pro vyhledávání do hloubky jsou zvláštním případem třídy stromů s klenbou , které se nazývají stromy Trémaux , pojmenované po objeviteli hloubkového průzkumu v 19. století.

Rozpětí stromů je důležité v paralelních a distribuovaných výpočtech jako způsob udržování komunikace mezi sadou procesorů; viz například Spanning Tree Protocol používaný zařízeními linkové vrstvy OSI nebo Shout (protokol) pro distribuované výpočty. Hloubkové a první metody pro konstrukci spanningových stromů na sekvenčních počítačích však nejsou vhodné pro paralelní a distribuované počítače. Místo toho vědci navrhli několik specializovanějších algoritmů pro hledání stromů v těchto modelech výpočtu.

Optimalizace

V některých oblastech teorie grafů je často užitečné najít strom minimální klenout o váženého grafu . Byly také studovány další optimalizační problémy na spanning trees, včetně maximálního spanning tree, minimálního stromu, který překlenuje alespoň k vrcholy, spanning stromu s nejmenším počtem hran na vrchol , spanning stromu s největším počtem listů , spanning stromu s nejmenším počtem listů (úzce souvisejících s problémem hamiltonovské cesty ), minimálním průměrem překlenujícím stromem a minimálním rozšířením překlenujícím stromem.

Byly studovány také problémy optimálního kostry pro konečné sady bodů v geometrickém prostoru, jako je euklidovská rovina . Pro takový vstup je spanning tree opět strom, který má jako vrcholy dané body. Kvalita stromu se měří stejným způsobem jako v grafu, přičemž se jako váha pro každou hranu používá euklidovská vzdálenost mezi dvojicemi bodů. Například euklidovský minimální kostra je tedy stejná jako minimální kostra grafu v úplném grafu s euklidovskými hranovými váhami. Pro vyřešení problému s optimalizací však není nutné tento graf konstruovat; například euklidovský problém s minimálním rozpětím lze efektivněji vyřešit v čase O ( n  log  n ) vytvořením Delaunayovy triangulace a poté aplikováním algoritmu minimálního rozpětí lineárního časového grafu na výslednou triangulaci.

Randomizace

Kostra kostry náhodně vybraná ze všech koster se stejnou pravděpodobností se nazývá jednotný kostra . Wilsonův algoritmus lze použít ke generování uniformních spanningových stromů v polynomiálním čase procesem náhodného procházení po daném grafu a mazání cyklů vytvořených tímto procházením.

Alternativním modelem pro generování spanningových stromů náhodně, ale ne rovnoměrně, je náhodný minimální spanningový strom . V tomto modelu jsou hranám grafu přiřazeny náhodné váhy a poté je sestaven minimální kostra váženého grafu.

Výčet

Protože graf může mít exponenciálně mnoho spanning stromů, není možné je všechny vypsat v polynomiálním čase . Algoritmy jsou však známé pro výpis všech spanningových stromů v polynomiálním čase na strom.

V nekonečných grafech

Každý konečný připojený graf má kostru. U nekonečně spojených grafů je však existence kosterních stromů ekvivalentní s axiomem volby . Nekonečný graf je připojen, pokud každá dvojice jeho vrcholů tvoří dvojici koncových bodů konečné cesty. Stejně jako u konečných grafů je strom spojeným grafem bez konečných cyklů a překlenovací strom lze definovat buď jako maximální acyklickou sadu hran, nebo jako strom, který obsahuje každý vrchol.

Stromy v grafu mohou být částečně uspořádány podle jejich podgrafického vztahu a jakýkoli nekonečný řetězec v tomto částečném pořadí má horní hranici (spojení stromů v řetězci). Zornovo lemma , jeden z mnoha ekvivalentních výroků k axiomu volby, vyžaduje, aby částečný řád, ve kterém jsou všechny řetězce horně ohraničeny, měl maximální prvek; v částečném pořadí na stromech grafu musí být tímto maximálním prvkem klenutý strom. Proto, pokud se předpokládá Zornovo lema, má každý nekonečný připojený graf spanning tree.

V opačném směru, vzhledem k rodině množin , je možné sestrojit nekonečný graf tak, aby každý spanningový strom grafu odpovídal volbě funkce rodiny množin. Proto pokud má každý nekonečný připojený graf spanning tree, pak je axiom výběru pravdivý.

V řízených multigrafech

Myšlenku kostry lze zobecnit na směrované multigrafy. Vzhledem k vrcholu v na řízeném multigrafu G je orientovaný spanningový strom T zakořeněný na v acyklický podgraf G, ve kterém má každý vrchol jiný než v přesahující 1. Tato definice je splněna pouze tehdy, když „větve“ T směřují k v .

Viz také

• Zaplavovací algoritmus
• Good spanning tree - Spanning tree for embedded planar graph

Reference