„Feszítőfa” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
aNincs szerkesztési összefoglaló |
Bizonyíték feszítőfa létezésére hozzáadása |
||
1. sor:
A [[gráfelmélet]] egy alapvető fogalma. A [[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át tartalmazó 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]] ([[Kruskal-algoritmus|Kruskal-algoritmussal]] kereshető) és a maximális költségű feszítőfa (módosított Kruskal-algoritmussal kereshető).
== Bizonyíték 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.
Nem összefüggő gráfokra: Az összefüggő gráfokra vonatkozó bizonyítást alkalmazzuk, külön külön minden egyes [[Gráfelméleti fogalomtár|komponensre]].
| |||