Magyar módszer
| Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. |
A magyar módszer egy algoritmus, segítségével páros gráfokban lehet maximális elemszámú párosítást keresni polinom időben. Harold Kuhn dolgozta ki az eljárást Kőnig Dénes és Egerváry Jenő munkája nyomán. Tiszteletükre magyar módszernek nevezte el.
Lépései szerkesztés
I. független élek felvétele, amíg lehet. Ezzel kapunk egy P párosítást.
II. javító út keresése és e mentén a párosítás növelése, amíg lehet.
Javító útnak nevezünk egy olyan utat, ami: két, párosításon kívüli csúcs között fut, a végpontjai a gráf különböző komponenseiben vannak és az élei váltakozva párosításon kívüli és párosításon belüliek.
Külső hivatkozások szerkesztés
|
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |