Kostra

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 19. září 2021; kontroly vyžadují 2 úpravy .

Kostra grafu je strom , podgraf daného grafu, se stejným počtem vrcholů jako původní graf. Neformálně řečeno, kostra se získá z původního grafu odstraněním maximálního počtu hran zahrnutých v cyklech, ale bez zničení konektivity grafu. Kostra zahrnuje všechny vrcholy původního grafu a obsahuje hranu. $n$ $n-1$

Definice

Kostra je acyklický souvislý podgraf daného souvislého neorientovaného grafu , který zahrnuje všechny jeho vrcholy .

Pojem rozprostírající se les je nejednoznačný; může znamenat jeden z následujících podgrafů:

jakýkoli acyklický podgraf obsahující všechny vrcholy grafu, ale nemusí být nutně spojen;
v nespojeném grafu, podgraf sestávající ze sjednocení kostry pro každou z jeho spojených komponent .

Kostra se také někdy nazývá kostra , kostra nebo kostra grafu . Přízvuk ve slově "ostovny" od různých autorů je uveden na první (od slova ostov) nebo na druhé slabice.

Vlastnosti

Jakýkoli kostra ve vrcholovém grafu obsahuje přesně hranu. $n$ $n-1$
Počet překlenovacích stromů v úplném grafu ve vrcholech se rovná tomuto tvrzení se nazývá Cayleyův vzorec [1] : $n$ $n^{n-2};$
Počet překlenovacích stromů v kompletním bipartitním grafu je $K_{{m,n}}$ $m^{n-1}\cdot n^{m-1}.$
Obecně lze počet kostrových stromů v libovolném grafu vypočítat pomocí tzv. věty o maticovém stromu .
Nechť je v grafu hrana Označme grafem získaným eliminací hrany a grafem získaným kontrakcí hrany do bodu. Pokud hrana není smyčka, pak platí následující vztah nazývaný delece-plus-contraction [2] : $\rho$ $\gamma .$ $\Gamma \zpětné lomítko \rho$ $\Gamma$ $\rho ,$ $\Gamma /\rho$ $\Gamma$ $\rho$ $\rho$ $\gamma ,$ $\tau (\Gamma )=\tau (\Gamma \zpětné lomítko \rho )+\tau (\Gamma /\rho ),$

kde označuje počet kostry v grafu

\tau (\Gamma )

\gamma .

Algoritmy

Spanning tree lze sestavit téměř jakýmkoliv algoritmem procházení grafu, jako je prohledávání do hloubky nebo prohledávání do šířky . Skládá se ze všech párů hran tak, že algoritmus při pohledu na vrchol najde nový, dříve neobjevený vrchol ve svém seznamu sousedství. $(u,v),$ $ty$ $v.$

Kostry vytvořené při procházení grafu z vrcholu Dijkstrovým algoritmem mají tu vlastnost, že nejkratší cesta v grafu od kteréhokoli jiného vrcholu je (je to také jediná) cesta z tohoto vrcholu v sestrojeném kostru. $s$ $s$ $s$

Existuje také několik paralelních a distribuovaných algoritmů spanning tree. Jako praktický příklad distribuovaného algoritmu lze uvést protokol STP .

Pokud je každé hraně grafu přiřazena váha (délka, cena atd.), pak se při hledání optimální kostry podílí četné algoritmy pro nalezení minimální kostry , což minimalizuje součet vah hran v něm obsažených. .

Problém nalezení kostry, ve které stupeň každého vrcholu nepřekročí nějakou předem určenou konstantu , je NP-úplný [3] . $k,$

Výběr kostry a počítání počtu vzdálených hran v grafech elektrických obvodů slouží k výpočtu počtu nezávislých obvodů při analýze elektrického obvodu metodou obvodových proudů [4] .

Viz také

Poznámky

↑ Martin Aigner, Günter M. Ziegler. Důkazy z knihy . - Springer-Verlag, 2004. - S. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Kolik stromů je v grafu // Kvant . - 2018. - č. 9 . - S. 9-13 . - doi : 10.4213/kvant20180902 . (Ruština)
↑ Michael R. Garey, David S. Johnson. Počítače a neovladatelnost: Průvodce teorií NP-úplnosti . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Teoretické základy elektrotechniky. Elektrické obvody. - M .: Gardariki, 2002. - 638 s. — ISBN 5-8297-0026-3 .