Magyar módszer

A Wikipédiából, a szabad enciklopédiából

A magyar módszer egy algoritmus, segítségével páros gráfokban lehet maximális 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]