Copac spanning

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 19 septembrie 2021; verificările necesită 2 modificări .

Arborele de acoperire al unui grafic este un arbore , un subgraf al unui grafic dat, cu același număr de vârfuri ca și graficul original. Informal vorbind, un spanning tree se obține din graficul original prin eliminarea numărului maxim de muchii incluse în cicluri, dar fără a întrerupe conectivitatea graficului. Arborele de acoperire include toate vârfurile graficului original și conține o muchie. $n$ $n-1$

Definiție

Un arbore spanning este un subgraf conex aciclic al unui graf nedirecționat conex dat , care include toate vârfurile sale .

Conceptul de pădure care se întinde este ambiguu; poate însemna unul dintre următoarele subgrafe:

orice subgraf aciclic care conține toate vârfurile grafului, dar nu neapărat conectate;
într-un graf deconectat, un subgraf constând din uniunea arborilor care se întind pentru fiecare dintre componentele sale conectate .

Un arbore spanning este, de asemenea, numit uneori spanning tree , spanning tree sau schelet grafic . Accentul din cuvântul „ostovny” de către diferiți autori este indicat pe prima (din cuvântul ostov) sau pe a doua silabă.

Proprietăți

Orice arbore de întindere dintr-un grafic de vârf conține exact o muchie. $n$ $n-1$
Numărul de arbori care se întind dintr-un grafic complet la vârfuri este egal cu această afirmație se numește formula Cayley [1] : $n$ $n^{n-2};$
Numărul de arbori care se întind dintr-un grafic bipartit complet este $K_{{m,n}}$ $m^{n-1}\cdot n^{m-1}.$
În general, numărul de arbori care se întind dintr-un grafic arbitrar poate fi calculat folosind așa-numita teoremă a arborelui matrice .
Să existe o muchie într-un grafic .Notați prin graficul obținut din eliminarea muchiei și prin graficul obținut din contracția muchiei la un punct. Dacă muchia nu este o buclă în, atunci următoarea relație este adevărată, numită ștergere-plus-contracție [2] : $\rho$ $\gamma .$ $\Gamma \backslash \rho$ $\Gamma$ $\rho ,$ $\Gamma /\rho$ $\Gamma$ $\rho$ $\rho$ $\gamma ,$ $\tau (\Gamma)=\tau (\Gamma \backslash \rho)+\tau (\Gamma /\rho),$

unde denotă numărul de arbori care se întind din grafic

\tau (\Gamma )

\gamma .

Algoritmi

Un arbore de întindere poate fi construit de aproape orice algoritm de traversare a graficului, cum ar fi căutarea în adâncime - prima căutare sau căutarea pe lățimea întâi . Este alcătuit din toate perechile de muchii astfel încât algoritmul, uitându-se la un vârf , găsește un vârf nou, nedescoperit anterior în lista sa de adiacență. $(u,v),$ $tu,$ $v.$

Arborii de întindere construiți atunci când parcurgeți un grafic dintr-un vârf prin algoritmul lui Dijkstra au proprietatea că cea mai scurtă cale din grafic de la orice alt vârf este (este și singura) cale de la acest vârf în arborele de întindere construit. $s$ $s$ $s$

Există, de asemenea, mai mulți algoritmi de arbore de acoperire paraleli și distribuiti. Ca exemplu practic de algoritm distribuit, poate fi dat protocolul STP .

Dacă fiecărei margini a graficului i se atribuie o pondere (lungime, cost etc.), atunci numeroși algoritmi pentru găsirea arborelui de întindere minim sunt implicați în găsirea arborelui de întindere optim, care minimizează suma greutăților muchiilor incluse în acesta. .

Problema găsirii unui arbore spanning în care gradul fiecărui vârf să nu depășească o constantă predeterminată este NP-complet [3] . $k,$

Selectarea arborelui de întindere și numărarea numărului de muchii îndepărtate în graficele circuitelor electrice este utilizată pentru a calcula numărul de circuite independente în analiza circuitului electric prin metoda curenților de circuit [4] .

Vezi și

Teorema arborelui matriceal
Arborele de întindere minim
Teorema numărului de arbori a lui Cayley
STP este un protocol de canal.

Note

↑ Martin Aigner, Günter M. Ziegler. Dovezi din carte . - Springer-Verlag, 2004. - P. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Câți arbori sunt într-un grafic // Kvant . - 2018. - Nr 9 . - S. 9-13 . - doi : 10.4213/kvant20180902 . (Rusă)
↑ Michael R. Garey, David S. Johnson. Calculatoare și intractabilitate: un ghid pentru teoria NP-completeității . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Fundamentele teoretice ale ingineriei electrice. Circuite electrice. - M . : Gardariki, 2002. - 638 p. — ISBN 5-8297-0026-3 .