Feszítőfa
A feszítőfa a gráfelmélet egy alapvető fogalma. Egy gráf feszítőfája a gráf minden csúcsát tartalmazó fa részgráf. Minden összefüggő gráfnak van feszítőfája. Minden gráfnak van feszítő erdője. A feszítő erdő az egyes komponensek feszítőfáiból á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 költségű feszítőfa (pl. a Kruskal-algoritmussal kereshető) és a maximális költségű feszítőfa (módosított Kruskal-algoritmussal kereshető).
Bizonyítás feszítőfa, feszítőerdő létezésére
[szerkesztés]Összefüggő gráfokra: Ha van kör a gráfban, annak egy élét elhagyva ugyanazon 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ő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.
Nem összefüggő gráfokra: Az összefüggő gráfokra vonatkozó bizonyítást alkalmazzuk, külön-külön minden egyes komponensre.
Források
[szerkesztés]Fleiner Tamás egyetemi docens "A számítástudomány alapjai" http://www.cs.bme.hu/~fleiner/jegyzet/NESZ.pdf
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
