Feszítőfa
 |
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
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