„Minimális 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
link |
Tulajdonságok: multiplicitás |
||
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 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==
===Multiplicitás===
Ha egy gráfban minden él költsége különböző, akkor a feszítő fa egyértelmű. Ha vannak egyező súlyú élek, akkor ez már nem egyértelmű. Ha például a gráf összes élének költsége ugyanannyi, akkor a gráf összes feszítő fája minimális feszítő fa.
Az összes élsúly különbözősége esetére az egyértelműség indirekt úton bizonyítható:
Legyen ''T''<sub>1</sub> és ''T''<sub>2</sub> is minimális súlyú feszítő fa.
==Lásd még==
* [[Gráf]]
| |||