„Minimális 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
a ISBN/PMID link(ek) sablonba burkolása MediaWiki RfC alapján
Krachi9 (vitalap | szerkesztései)
Feszítőfa hivatkozás hozzáadása
1. sor:
[[Fájl:Minimum spanning tree.svg|bélyegkép|jobbra|300px|Egy minimális feszítőfa]]
A '''minimális költségű [[feszítőfa]]''' vagy '''minimális feszítőfa''' (angolul ''minimum spanning tree'') egy összefüggő, irányítatlan [[gráf]]ban található legkisebb [[élsúly]]ú [[feszítőfa]]. A feszítőfa egy olyan [[fa (gráfelmélet)|fa]], ami a gráf összes csúcsát tartalmazza és élei az eredeti gráf élei közül valók. A minimális feszítőfa nem feltétlenül egyértelmű, de annak súlya igen. Egy gráf tetszőleges minimális feszítőfájának keresésére használható [[Kruskal-algoritmus|Kruskal]] és [[Prim-algoritmus|Prim]] [[algoritmus]]a.
 
==Tulajdonságai==