Magyar módszer

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont!
Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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

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.