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

[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
A forrást nem a cikk legelejére tesszük. A lábjegyzetekkel az adott állítást vagy bekezdést forrásoljuk, lehetőleg az oldalszámot is megjelölve
2. sor:
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 (gráfelmélet)|fa]] [[részgráf]]. Minden [[összefüggő gráf]]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á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 feszítőfa|minimális költségű feszítőfa]] (pl. a [[Kruskal-algoritmus]]sal kereshető) és a maximális költségű feszítőfa (módosított Kruskal-algoritmussal kereshető).
 
== BizonyítékBizonyítás feszítőfa, feszítőerdő létezésére ==
Ö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ő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.