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.

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:

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

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

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.

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.

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] .

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

  1. Martin Aigner, Günter M. Ziegler. Bizonyítékok a könyvből . - Springer-Verlag, 2004. - P.  173-178 . ISBN 978-3540404606 .
  2. Petrunin A. Hány fa van egy gráfban  // Kvant . - 2018. - 9. sz . - S. 9-13 . - doi : 10.4213/kvant20180902 .
  3. 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 .
  4. Bessonov L. A. Az elektrotechnika elméleti alapjai. Elektromos áramkörök. - M . : Gardariki, 2002. - 638 p. — ISBN 5-8297-0026-3 .