„Feszítőfa” változatai közötti eltérés

A '''feszítőfa''' a [[gráfelmélet]] egy alapvető fogalma. AEgy [[gráf]] feszítőfája a gráf minden csúcsát tartalmazó [[Fa (gráfelmélet)|fa]] [[részgráf]]. Minden [[összefüggő gráf]]<nowiki/>nak van feszítőfája. Minden gráfnak van feszítő [[Erdő (gráfelmélet)|erdője]]. A [[feszítő erdő]] az egyes komponensek feszítőfájátfeszítőfáiból tartalmazóálló részgráf. Egy gráfnak több feszítőfája is lehetséges. Speciális feszítőfák például a [[Minimális feszítőfa|minimális költségű feszítőfa]] (pl. a [[Kruskal-algoritmus|Kruskal-algoritmussal]]sal kereshető) és a maximális költségű feszítőfa (módosított Kruskal-algoritmussal kereshető).

Összefüggő gráfokra: Ha van [[Kör (gráfelmélet)|kör]] a gráfban, annak egy [[Gráfelméleti fogalomtár|élét]] elhagyva ugyan azon [[Gráfelméleti fogalomtár|csúcsokat]] tartalmazó összefüggő gráfot kapunk. Ezt folytatva amíg csak lehet, egy olyan gráfot kapunk, amely az összes eredeti csúcsot tartalmazza, ugyanis csak körbölkörből hagytunk el éleket, így a csúcsok száma nem változott, összefüggő lesz, mivel nem vettünk el olyan éleket a gráfból amik nem alkottak kört. Ez alapján a megmaradt gráf egy feszítőfája lesz az eredeti gráfnak.