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

[ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló
Krachi9 (vitalap | szerkesztései)
Forrás hozzáadása
1. sor:
{{nincs forrás}}
<ref>http://www.cs.bme.hu/~fleiner/jegyzet/NESZ.pdf</ref>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ék feszítőfa, feszítőerdő létezésére ==