Spanning Tree

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 september 2021; kontroller kräver 2 redigeringar .

En grafs spännträd är ett träd , en subgraf till en given graf, med samma antal hörn som den ursprungliga grafen. Informellt sett erhålls ett spännträd från den ursprungliga grafen genom att ta bort det maximala antalet kanter som ingår i cyklerna, men utan att bryta grafens anslutning. Spännträdet inkluderar alla hörn i den ursprungliga grafen och innehåller en kant. $n$ $n-1$

Definition

Ett spännträd är en acyklisk sammankopplad subgraf av en given sammankopplad oriktad graf som inkluderar alla dess hörn .

Konceptet med en spännande skog är tvetydigt; det kan betyda en av följande undergrafer:

en acyklisk subgraf som innehåller alla hörn i grafen, men som inte nödvändigtvis är sammankopplade;
i en frånkopplad graf, en subgraf som består av föreningen av spännträd för var och en av dess anslutna komponenter .

Ett spannträd kallas också ibland ett spannträd , spannträd eller grafskelett . Betoningen i ordet "ostovny" av olika författare anges på den första (från ordet ostov) eller på den andra stavelsen.

Egenskaper

Varje spännträd i en vertexgraf innehåller exakt en kant. $n$ $n-1$
Antalet spännande träd i en komplett graf vid hörnen är lika med detta uttalande kallas Cayley-formeln [1] : $n$ $n^{n-2};$
Antalet spännande träd i en komplett tvådelad graf är $K_{{m,n}}$ $m^{n-1}\cdot n^{m-1}.$
I allmänhet kan antalet spännande träd i en godtycklig graf beräknas med hjälp av den så kallade matristrädsatsen .
Låt det finnas en kant i en graf Beteckna med grafen som erhålls från elimineringen av kanten och med grafen som erhålls från sammandragningen av kanten till en punkt. Om kanten inte är en loop in är följande relation sann, kallad deletion-plus-kontraktion [2] : $\rho$ $\gamma .$ $\Gamma \backslash \rho$ $\Gamma$ $\rho ,$ $\Gamma /\rho$ $\Gamma$ $\rho$ $\rho$ $\gamma ,$ $\tau (\Gamma )=\tau (\Gamma \backslash \rho )+\tau (\Gamma /\rho ),$

där anger antalet spännande träd i grafen

\tau (\Gamma )

\gamma .

Algoritmer

Ett spännträd kan byggas med nästan vilken grafgenomgångsalgoritm som helst, till exempel djup - först-sökning eller bredd-först-sökning . Den består av alla par av kanter så att algoritmen, tittar på en vertex , hittar en ny, tidigare oupptäckt vertex i dess närliggande lista. $(u,v),$ $u,$ $v.$

Spännande träd som byggs när man korsar en graf från en vertex med Dijkstras algoritm har egenskapen att den kortaste vägen i grafen från till någon annan vertex är (det är också den enda) vägen från till denna vertex i det konstruerade spännträdet. $s$ $s$ $s$

Det finns också flera parallella och distribuerade spännträdsalgoritmer. Som ett praktiskt exempel på en distribuerad algoritm kan STP- protokollet ges .

Om varje kant av grafen tilldelas en vikt (längd, kostnad, etc.), är många algoritmer för att hitta det minsta spännträdet involverade i att hitta det optimala spännträdet, vilket minimerar summan av vikterna av kanterna som ingår i det .

Problemet med att hitta ett spännträd där graden av varje vertex inte överstiger någon förutbestämd konstant , är NP-komplett [3] . $k,$

Valet av spännträdet och räkningen av antalet avlägsna kanter i graferna för elektriska kretsar används för att beräkna antalet oberoende kretsar i analysen av den elektriska kretsen med metoden för kretsströmmar [4] .

Se även

Anteckningar

↑ Martin Aigner, Günter M. Ziegler. Bevis från boken . - Springer-Verlag, 2004. - S. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Hur många träd finns i en graf // Kvant . - 2018. - Nr 9 . - S. 9-13 . - doi : 10.4213/kvant20180902 . (ryska)
↑ Michael R. Garey, David S. Johnson. Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Teoretiska grunder för elektroteknik. Elektriska kretsar. - M . : Gardariki, 2002. - 638 sid. — ISBN 5-8297-0026-3 .