„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 |
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==
|