Kőnig-Hall-tétel

1. Sablon:Label

Kőnig–Hall-tétel

A **Kőnig–Hall-tétel** a gráfelmélet és a kombinatorika egyik alapvető eredménye, amely két részhalmaz közötti párosítások létezésének feltételét adja meg.

A tétel megfogalmazása

Legyen $G=(U\cup V,E)$ egy bipartit gráf, ahol $U$ és $V$ a két partíció (csúcsok halmazai), és $E$ az élek halmaza. Ekkor létezik $U$-ból $V$-be vezető teljes párosítás pontosan akkor, ha az alábbi **Hall-feltétel** teljesül:

$\mathrm{\forall }S\subseteq U:|N(S)|\ge |S|,$

ahol $N(S)$ az $S$-ben lévő csúcsok szomszédainak halmaza $V$-ben.

Magyarázat

A Kőnig–Hall-tétel azt mondja ki, hogy egy bipartit gráfban létezhet $U$ halmaz elemeire nézve egy olyan teljes párosítás, amely az $U$ minden csúcsát összeköti pontosan egy $V$-beli csúccsal, ha minden $U$-beli részhalmazra igaz, hogy a szomszédsági halmaza (a hozzá kapcsolódó $V$-beli csúcsok) legalább olyan nagy, mint maga a részhalmaz.

• **Teljes párosítás:** Olyan élhalmaz, amelyben minden $U$-beli csúcs pontosan egy $V$-beli csúccsal van összekötve.
• **Hall-feltétel:** Ez a feltétel biztosítja, hogy az $U$-beli csúcsokhoz mindig található elegendő "szabad" $V$-beli csúcs, hogy a párosítás létrejöhessen.

Példa

Tegyük fel, hogy egy iskola tanulóit ($U$) és tanárait ($V$) akarjuk összepárosítani, hogy minden tanuló pontosan egy tanárt kapjon. Az élek ($E$) azt jelölik, hogy mely tanárok taníthatják az adott tanulót.

Ha minden tanuló számára van legalább annyi lehetséges tanár, mint ahányan a tanulók vannak az adott csoportban, akkor a Kőnig–Hall-tétel szerint létezhet egy teljes párosítás.

• Példa adatok:

 * $U=\{A,B,C\}$, $V=\{X,Y,Z\}$,
 * Élek: $E=\{(A,X),(A,Y),(B,Y),(B,Z),(C,X)\}$.

 Ellenőrizzük a Hall-feltételt:
 * $S=\{A\}$: $N(S)=\{X,Y\}$, tehát $|N(S)|=2\ge |S|=1$.
 * $S=\{A,B\}$: $N(S)=\{X,Y,Z\}$, tehát $|N(S)|=3\ge |S|=2$.
 * $S=\{A,B,C\}$: $N(S)=\{X,Y,Z\}$, tehát $|N(S)|=3\ge |S|=3$.

 Mivel minden részhalmazra teljesül a Hall-feltétel, létezik egy teljes párosítás.

Következmények

A Kőnig–Hall-tétel több fontos alkalmazással rendelkezik:

• **Projektmunkák kiosztása:** Tanulók és projektek párosítása a preferenciák alapján.
• **Házassági probléma:** A tétel alapját képezi az ún. "házassági problémának", amely azt vizsgálja, hogy egy bipartit gráfban létezik-e teljes párosítás.
• **Áramláselmélet:** A tétel szorosan kapcsolódik a maximális áramlás és minimális vágás problémájához.

További megjegyzések

• A tétel a bipartit gráfokra vonatkozik, de általánosítható más típusú párosítási problémákra.
• A tételt Dénes Kőnig és Philip Hall függetlenül fedezték fel.
• A Kőnig–Hall-tétel algoritmikus szempontból is fontos, mivel segít hatékony párosítási algoritmusok kidolgozásában.