12.2. 12.2. A feladat matematikai vizsgálata

A „házasság” feladat egzisztencia formájára vonatkozik az alábbi tétel.

KŐNIG tétel

Adott kvalifikációs táblázat esetén

Más szavakkal megfogalmazva: vagy az összes személy hozzárendelhető a munkákhoz, vagy ha nem, akkor megadható a személyeknek olyan részhalmaza, hogy ezen személyek száma meghaladja azon munkák számát, amelyeket együttesen el tudnak látni.

Nem nehéz belátni, hogy a „házasság” feladat az általános Kőnig feladatnak olyan speciális eseteként fogható fel, ahol minden és minden . Ezért a tétel bizonyítását nem ismételjük meg. A bizonyításban szereplő folyamfeladatban az 1 értékű kapacitások miatt az típusú éleken a folyam csak 0 vagy 1 lehet. Ha az élen a folyam 1, akkor az személy hozzá van rendelve a munkához, 0 folyam esetén nincs.

A ”házasság” feladat egzisztencia formájára kimondott KŐNIG tétel átfogalmazható a következőképpen

KŐNIG tétel (más formában):

Adott kvalifikációs táblázat esetén az összes személy munkához való hozzárendelhetőségének szükséges és elégséges feltétele az, hogy minden személy esetén

Természetesen a két egzisztencia tétel ekvivalens egymással, az először megfogalmazott viszont a alaptételünkhöz, a MINTY tételhez hasonló szerkezetű.