„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
→Tulajdonságai: minimális költségű él |
Algoritmusok |
||
22. sor:
===Minimális költségű él===
Ha a gráfban van egy egyértelmű legkisebb költségű él, akkor a gráf minimális költségű feszítő fáinak mindegyike tartalmazni fogja ezt az élt. Különben a vágásokra alkalmazott érveléssel kimutatható, hogy az adott feszítő fa nem minimális költségű.
==Algoritmusok==
A legismertebb feszítő fa algoritmusok a [[Kruskal-algoritmus]] és a [[Prim-algoritmus]]. Mindkettő mohón épít egy minimális feszítő fát. A Kruskal-algoritmus kezdetben az összes pontot tekinti, a Prim-algoritmus pedig egy kezdőpontot. Innen elindulva éleket hozzávéve készítik el a fát.
A fordított mohó algoritmus, másik nevén óvatos algoritmus éleket töröl, mégpedig minden körből törli a legnagyobb költségű élt. A vegyes algoritmus <!--Még meg kell nézni, hogy hívják, nem ez az igazi neve-->két oldalról közelíti a feszítő fát. Egyrészt épít egy erdőt, másrészt éleket töröl a körökből.
==Lásd még==
* [[Gráf]]
| |||