Feszítőfának

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 19-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A gráf feszítőfája egy fa , egy adott gráf részgráfja, amelynek csúcsai ugyanannyiak, mint az eredeti gráfnak. Informálisan szólva, egy feszítőfát kapunk az eredeti gráfból úgy, hogy eltávolítjuk a ciklusokban szereplő élek maximális számát, de anélkül, hogy megszakítanák a gráf összekapcsolhatóságát. A feszítőfa tartalmazza az eredeti gráf összes csúcsát, és tartalmaz egy élt. $n$ $n-1$

Definíció

A feszítőfa egy adott összefüggő irányítatlan gráf aciklikus összefüggő részgráfja , amely tartalmazza annak összes csúcsát .

Az átívelő erdő fogalma nem egyértelmű, a következő algráfok egyikét jelentheti:

bármely aciklikus részgráf, amely a gráf összes csúcsát tartalmazza, de nem feltétlenül kapcsolódik;
szétválasztott gráfban egy részgráf, amely a feszítőfák uniójából áll az egyes kapcsolódó összetevőihez .

A feszítőfát néha feszítőfának , feszítőfának vagy gráfváznak is nevezik . Az "ostovny" szóban a különböző szerzők által használt hangsúly az első (az ostov szóból) vagy a második szótagon van feltüntetve.

Tulajdonságok

A csúcsgráf bármely feszítőfája pontosan tartalmaz egy élt. $n$ $n-1$
A teljes gráf csúcsaiban lévő feszítőfák száma megegyezik ezzel az állítással, amelyet Cayley-képletnek neveznek [1] : $n$ $n^{n-2};$
A feszítőfák száma egy teljes bipartit gráfban a $K_{{m,n}}$ $m^{n-1}\cdot n^{m-1}.$
Általánosságban elmondható, hogy egy tetszőleges gráfban lévő feszítőfák száma kiszámítható az úgynevezett mátrixfa tétel segítségével .
Legyen egy él a gráfban Jelöljük az él eliminációjából kapott gráfgal és az élnek egy pontra való összehúzódásából kapott gráfgal. Ha az él nem hurok, akkor a következő reláció igaz, amelyet törlés-plusz-összehúzódásnak neveznek [2] : $\rho$ $\gamma .$ $\Gamma \backslash \rho$ $\Gamma$ $\rho ,$ $\Gamma /\rho$ $\Gamma$ $\rho$ $\rho$ $\gamma ,$ $\tau (\Gamma )=\tau (\Gamma \backslash \rho )+\tau (\Gamma /\rho ),$

ahol a feszítőfák számát jelöli a grafikonon

\tau (\Gamma )

\gamma .

Algoritmusok

Feszítőfát szinte bármilyen gráfbejárási algoritmussal fel lehet építeni, például a mélység - első keresés vagy a szélesség-első keresés . Minden élpárból áll, így az algoritmus egy csúcsra nézve egy új, korábban fel nem fedezett csúcsot talál a szomszédsági listájában. ${\megjelenítési stílus (u,v),}$ $te,$ $v.$

A Dijkstra-algoritmus által egy csúcsból egy gráf bejárása során felépített feszítőfák azzal a tulajdonsággal rendelkeznek, hogy a gráf legrövidebb útja bármely másik csúcshoz (egyben ez az egyetlen) az e csúcshoz vezető út a megszerkesztett feszítőfában. $s$ $s$ $s$

Számos párhuzamos és elosztott feszítőfa-algoritmus is létezik. Az elosztott algoritmus gyakorlati példájaként megadható az STP protokoll .

Ha a gráf minden éléhez hozzárendelünk egy súlyt (hossz, költség stb.), akkor a minimális feszítőfa megtalálásához számos algoritmus vesz részt az optimális feszítőfa megtalálásában, amely minimalizálja a benne szereplő élek súlyának összegét. .

Egy olyan feszítőfa megtalálásának problémája, amelyben az egyes csúcsok foka nem haladja meg valamelyik előre meghatározott állandót , NP-teljes [3] . $k,$

A feszítőfa kiválasztását és a távoli élek számának megszámlálását az elektromos áramkörök grafikonjaiban használják a független áramkörök számának kiszámításához az elektromos áramkör elemzése során az áramköri áramok módszerével [4] .

Lásd még

Jegyzetek

↑ Martin Aigner, Günter M. Ziegler. Bizonyítékok a könyvből . - Springer-Verlag, 2004. - P. 173-178 . — ISBN 978-3540404606 .
↑ Petrunin A. Hány fa van egy gráfban // Kvant . - 2018. - 9. sz . - S. 9-13 . - doi : 10.4213/kvant20180902 . (Orosz)
↑ Michael R. Garey, David S. Johnson. Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - S. 206 . — ISBN 0-7167-1045-5 .
↑ Bessonov L. A. Az elektrotechnika elméleti alapjai. Elektromos áramkörök. - M . : Gardariki, 2002. - 638 p. — ISBN 5-8297-0026-3 .