Kőnig alternáló utas algoritmus

Scope: Megkeresi a legnagyobb párosítást az adott $G = (S, T, V)$ páros gráfban.

Procedure.:

Induljunk ki egy tetszőleges $M$ párosításból.
Irányítsuk meg a $G$ éleit úgy, hogy az $M$ -beli élek $S$ -ből $T$ -be mutatnak, a többi él meg a másik irányba, azaz $T$ -ből $S$ -be.
Jelölje $R_{S}$ azon $S$ -beli csúcsok halmazát, melyeket nem fed $M$ .
Hasonlóan, jelölje $R_{T}$ azon $T$ -beli csúcsok halmazát, melyeket nem fed $M$ .
Keressünk egy utat $R_{S}$ -ből $R_{T}$ -be az irányított gráfban (ezek az alternáló utak).
Ha létezik ilyen út, akkor cseréljük le $M$ -et az alternáló út és $M$ szimmetrikus differenciájára.
Azaz az út minden páratlanadig élére.

Jegyzetek kincstára