12. fejezet - „Házasság” feladat (Egyszerű KŐNIG feladat)

12.1. 12.1. A feladat megfogalmazása

Legyenek adottak az személyek és a munkák. Adott továbbá, hogy mely személy mely munkához ért (melyik munkára van kvalifikálva). Ezt szokás az ún. kvalifikációs táblázattal megadni oly módon, hogy az cellába *-ot teszünk, ha az személy el tudja végezni a munkát. Az egyszerű Kőnig feladatot („házasság” feladatot ) az alábbi sémával szoktuk jellemezni:

A „házasság” feladat egzisztencia formában:

Hozzárendelhető-e a összes személy a munkákhoz az alábbi feltételekkel:

  • a személy értsen a munkához,

  • egy munkát csak egy személy láthat el?

A feladatot az alábbi megfogalmazás miatt nevezik „házasság” feladatnak. Legyenek adottak férfiakat és nők, akik között ismert a rokonszenv (szimpátia) táblázat. A kérdés annak eldöntése, hogy minden férfi meg tud-e nősülni úgy, hogy rokonszenves nővel kössön házasságot, kizárva a poligámiát.

A legtöbb esetben azonban nem csak arra vagyunk kíváncsiak, hogy megoldható-e a hozzárendelés, amennyiben nem tudjuk az összes személyt hozzárendelni, akkor jó lenne tudni, hogy maximálisan hány személy rendelhető a munkákhoz. Ha a személyek száma meghaladja a munkák számát, akkor eleve nem lehet az összes személyt hozzárendelni a munkákhoz, tehát az egzisztencia formában megfogalmazott feladat megoldása triviális, nem triviális azonban az olyan kérdésfelvetésre, hogy maximálisan hány személy rendelhető a munkákhoz.

A „házasság” feladat optimalizálási formában:

Maximálisan hány személy rendelhető a munkákhoz az alábbi feltételekkel:

  • a személy értsen a munkához,

  • egy személy csak egy munkához rendelhető,

  • egy munkát csak egy egy személy láthat el?

Mielőtt a feladat megoldására vonatkozó fontos állítást kimondanánk, ennek előkészítésére vezessük be az alábbi jelöléseket.

Legyen a személyek, a munkák halmaza. Jelölje a személyek egy tetszőleges részhalmazát és jelölje azon munkák halmazát, amelyekhez a P-beli személyek együttesen értenek. Jelölje továbbá a P-beli személyek számát, a -beli munkák számát.

Példaként tekintsük az alábbi kvalifikációs táblázattal adott egyszerű Kőnig feladatot:

Ha , ekkor , , .