Spændende træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. september 2021; checks kræver 2 redigeringer .

En grafs spændingstræ er et træ , en undergraf af en given graf, med det samme antal hjørner som den originale graf. Uformelt set opnås et spændingstræ fra den originale graf ved at fjerne det maksimale antal kanter, der er inkluderet i cyklusserne, men uden at bryde grafens forbindelse. Det spændende træ inkluderer alle hjørner af den originale graf og indeholder en kant. $n$ $n-1$

Definition

Et spændingstræ er en acyklisk forbundet undergraf af en given forbundet urettet graf , der inkluderer alle dens hjørner .

Konceptet med en spændende skov er tvetydigt; det kan betyde en af følgende undergrafer:

enhver acyklisk undergraf, der indeholder alle grafens toppunkter, men som ikke nødvendigvis er forbundet;
i en frakoblet graf, en undergraf, der består af foreningen af spændingstræer for hver af dens forbundne komponenter .

Et spændingstræ kaldes også nogle gange et spændingstræ , spændingstræ eller grafskelet . Betoningen i ordet "ostovny" af forskellige forfattere er angivet på den første (fra ordet ostov) eller på den anden stavelse.

Egenskaber

Ethvert spændingstræ i en toppunktsgraf indeholder nøjagtigt en kant. $n$ $n-1$
Antallet af spændende træer i en komplet graf ved toppunkterne er lig med dette udsagn kaldes Cayley-formlen [1] : $n$ $n^{n-2};$
Antallet af spændende træer i en komplet todelt graf er $K_{{m,n}}$ $m^{n-1}\cdot n^{m-1}.$
Generelt kan antallet af spændende træer i en vilkårlig graf beregnes ved hjælp af den såkaldte matrixtræsætning .
Lad der være en kant i en graf Betegn med grafen opnået fra elimineringen af kanten og med grafen opnået fra sammentrækningen af kanten til et punkt. Hvis kanten ikke er en sløjfe, er følgende relation sand, kaldet sletning-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 ),$

hvor angiver antallet af spændende træer i grafen

\tau (\Gamma )

\gamma .

Algoritmer

Et spændingstræ kan bygges af næsten enhver grafgennemløbsalgoritme, såsom dybde - først-søgning eller bredde-først-søgning . Den består af alle par af kanter , således at algoritmen, ser på et toppunkt , finder et nyt, tidligere uopdaget toppunkt i dens tilgrænsende liste. $(u,v),$ $u,$ $v.$

Spændende træer bygget, når man krydser en graf fra et toppunkt med Dijkstras algoritme , har den egenskab, at den korteste vej i grafen fra til ethvert andet vertex er (det er også den eneste) vej fra til dette toppunkt i det konstruerede spændingstræ. $s$ $s$ $s$

Der er også flere parallelle og distribuerede spændingstræ-algoritmer. Som et praktisk eksempel på en distribueret algoritme kan STP -protokollen gives .

Hvis hver kant af grafen tildeles en vægt (længde, pris osv.), så er adskillige algoritmer til at finde det mindste spændingstræ involveret i at finde det optimale spændingstræ, hvilket minimerer summen af vægtene af kanterne, der er inkluderet i det .

Problemet med at finde et spændingstræ, hvor graden af hvert toppunkt ikke overstiger en forudbestemt konstant , er NP-komplet [3] . $k,$

Udvælgelsen af spændingstræet og optælling af antallet af fjerne kanter i graferne for elektriske kredsløb bruges til at beregne antallet af uafhængige kredsløb i analysen af det elektriske kredsløb ved metoden med kredsløbsstrømme [4] .

Se også

Noter

↑ Martin Aigner, Günter M. Ziegler. Beviser fra bogen . - Springer-Verlag, 2004. - S. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Hvor mange træer er der i en graf // Kvant . - 2018. - Nr. 9 . - S. 9-13 . - doi : 10.4213/kvant20180902 . (Russisk)
↑ Michael R. Garey, David S. Johnson. Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Teoretisk grundlag for elektroteknik. Elektriske kredsløb. - M . : Gardariki, 2002. - 638 s. — ISBN 5-8297-0026-3 .