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