12.3. 12.3. Kőnig-Egerváry tétel

Az általános Kőnig feladatnál ismertetett lefedési probléma itt is értelmezhető a következők szerint. A „házasság” feladatban a fedővonalrendszer súlyszáma a fedővonalak számának, a folyamfeladat maximuma pedig a hozzárendelések maximális számának felel meg. Legyen adott egy táblázatunk, amelyben *-ok szerepelnek. Fedővonalrendszer alatt a táblázat bizonyos sorainak ill. oszlopainak egy-egy vonallal való lefedését értjük.

Lefedési feladat:

Fedjük le a táblázatban szereplő összes *-ot a legkevesebb számú fedővonalrendszerrel!

A FORD-FULKERSON tétel átfogalmazása szerint a fedővonalak minimális száma megegyezik a hozzárendelések maximális számával. Ezt a tételt KŐNIG-EGERVÁRY tétel [ 1 ], [ 9 ] néven ismeri a szakirodalom. A történeti hűséghez hozzátartozik, hogy a KŐNIG-EGERVÁRY tétel az 1930-as években keletkezett, míg a folyamokra vonatkozó FORD-FULKERSON tétel az 1960-as években lett kidolgozva. Mi tárgyalásmódunk fordított, az általánosabb tételből vezetjük le az egyébként nagy horderejű KŐNIG-EGERVÁRY tételt. Ennek a tételnek fontos szerepe volt a „magyar módszer” kidolgozásánál.

A történeti hűség miatt az alábbiakban közöljük az 1930-as években már ismert, vonatkozó eredményeket:

Tekintsünk egy -es mátrixot, amelynek elemei 0 és 1. Az 1-esek egy részhalmazát függetlennek nevezzük, ha nem fekszik kettő közülük ugyanazon sorban ill. oszlopban. Fedővonalrendszer alatt az összes 1-est lefedő vonalakat (vízszintes vagy függőleges) értjük.

LEMMA:

A független 1-esek száma nem lehet nagyobb az összes 1-est lefedő fedővonalak számánál.

KŐNIG-EGERVÁRY tétel:

A független 1-esek maximális száma megegyezik az összes 1-est lefedő fedővonalak minimális számával.

Tehát akár a maximális független 1-esek, akár az összes 1-est lefedő vonalak minimális számának meghatározása a feladatunk, az alábbiakban ismertetésre kerülő algoritmussal megkapjuk az eredményt.