Hall-tétel
A matematikában a Hall-tétel (1935, Philip Hall) egy kombinatorikai állítás, ami feltételt ad arra, hogy mikor lehet kiválasztani egy adott halmaz valahány nem feltétlenül diszjunkt részhalmazából különböző elemeket.
Legyen S = {S1, S2, … } egy (nem feltétlenül megszámlálható) halmaza egy M halmaz véges részhalmazainak. A diszjunkt reprezentáns rendszer (innentől DRR) egy olyan X = {x1, x2, …} halmaza M-beli páronként diszjunkt elemeknek, melyekre |X| = |S|, és minden i-re xi eleme Si-nek teljesül.
Az S halmaz teljesíti a Hall-feltételt, ha S minden T = {Ti } részhalmazára:
- (vagyis bármely n részhalmaz együtt legalább n elemből áll)
A Hall-tétel azt állítja, hogy akkor és csak akkor létezik diszjunkt reprezentáns rendszer X = {xi}, ha S teljesíti a Hall-feltételt.
Például: Legyen S1 = {1, 2, 3}, S2 = {1, 4, 5}, S3 = {3, 5}.
Erre az S = {S1, S2, S3} halmazra, egy megfelelő DRR az {1, 4, 5} (Nem csak ez az egy DRR lehetséges: a {2, 1, 3} ugyanúgy jó lenne).
A leggyakoribb példa a Hall-tétel alkalmazására, ha elképzelünk egy-egy n tagú férfiakból, illetve nőkből álló csoportot. Minden nő boldogan hozzámenne a férfiak egy bizonyos részhalmazához, és minden férfi boldogan elvenne bármely nőt, aki hozzá akarna menni. Gondoljuk meg, mikor lenne lehetséges úgy összeházasítani a férfiakat a nőkkel, hogy mindenki boldog legyen.
Ha Mi lesz az a halmaza a férfiaknak, akikkel az i-edik nő boldogan összeházasodna, akkor a tétel állítása szerint akkor és csak akkor tudna minden nő boldogan férjhez menni, ha az {Mi} halmazok halmaza kielégíti a Hall-feltételt.
A Hall-feltétel jelen esetben bármely részhalmazára a nőknek, azon férfiak száma, akik az -beli nők közül legalább egyet elvennének () legyen legalább akkora, mint a nők ezen részhalmazának elemszáma, . Az természetes, hogy a feltétel szükséges, hiszen enélkül nem lenne elég az -beli nők között szétosztható férfi. Annál érdekesebb, hogy a feltétel elégséges is.
A tételnek vannak egyéb alkalmazásai is. Például vegyünk egy csomag francia kártyát, és osszuk szét őket 13 darab csoportba, minden csoportba 4-et téve. Ezek után a Hall-tételt használva láthatjuk, hogy lehetséges minden csoportból 1-1 kártyát úgy kiválasztani, hogy a 13 kiválasztott kártya közül minden kártyaértékből pontosan 1 szerepeljen (ász, 2, 3, …, dáma, király).
Absztraktabb példaként legyen G egy csoport és H egy véges részcsoportja G-nek. Ekkor a tétel segítségével megmutathatjuk, hogy létezik olyan X halmaz, ami egyaránt DRR-je a H G-beli jobb és bal oldali mellékosztályainak.
A tétel a megbízatási problémára is alkalmazható: Adott n alkalmazott halmaza, és mindhez egy lista, hogy kit mire lehet alkalmazni. Akkor és csak akkor tudunk mindenkinek a képességeihez megfelelő munkát adni, ha k (1…n) minden értékére bármely k db lista összesen legalább k db munkát tartalmaz.
A még általánosabb problémára, melyben (nem feltétlenül különböző) elemeket kell kiválasztani halmazok egy halmazából, általában csak a csoportaxiómákat feltéve alkalmazhatjuk.
Bizonyítás
szerkesztésA Hall-tétel véges esetét fogjuk az |S|-re, azaz elemszámára vonatkozó indukcióval bizonyítani. A végtelen eset a kompaktsági tétel segítségével történik.
A tétel triviálisan igaz az |S| = 0 esetben.
Feltesszük, hogy a tétel minden |S| < n értékre igaz, ekkor |S| = n-re bizonyítunk.
Először nézzük, mi van akkor, ha az alábbi erősebb feltételt tesszük fel minden -re. Vegyük bármely -et is reprezentánsának; a DRR-t -ből kell választanunk. De, ha , akkor a feltevésünk szerint . A tétel már bizonyított esetét -re alkalmazva látható, hogy találhatunk megfelelő DRR-t -höz.
Egyébként bizonyos értékekre az éles egyenlőség áll fent . -n belül már bármely -re beláttuk -t, így a tétel már bizonyított esete alapján választhatunk DRR-t számára. Az maradt hátra, hogy találjunk egy DRR-t -hez, ami nélkülözi összes elemét (ezek az elemek SDR-ében vannak benne). Ahhoz, hogy (újfent) fel tudjuk használni a tétel már bizonyított esetét, meg kell mutatnunk, hogy bármely -re, elemeinek figyelembe vétele nélkül is marad elég elem -ben: azaz -t kell belátnunk.
De
,
és diszjunktságát felhasználva. Így a tétel már bizonyított esetét felhasználva látható, hogy -hez tényleg létezik megfelelő DRR, amely egyetlen elemét sem tartalmazza.
Ezzel bebizonyítottuk a tételt.
Következmény
szerkesztésHa egy páros gráf, akkor -ben akkor és csak akkor van -et lefedő párosítás, ha minden részhalmazra.
Gráfelmélet
szerkesztésA Hall-tételnek főleg a gráfelméleten belül vannak alkalmazásai. Gráfelméleti problémaként így fogalmazhatjuk meg az alapkérdést:
Adott egy páros gráf, G:= (S + T, E), két ugyanakkora méretű csúcshalmazzal, S-sel és T-vel, a kérdés pedig az, hogy létezik-e G-ben teljes párosítás.
A Hall-tétel megadja a választ:
Jelentse a G-beli X csúcshalmaz szomszédainak számát. A Hall-tétel szerint akkor és csak akkor létezik teljes párosítás G-ben, ha S minden X részhalmazára
A tetszőleges gráfokra történő általánosítást a Tutte-tétel teszi lehetővé.
Egy még általánosabb állítás
szerkesztésLegyen G egy páros gráf, BIPN(X,Y) úgy, hogy X és Y nem feltétlenül azonos méretűek. Ilyenkor G-ben akkor és csak akkor párosíthatók X összes csúcsai Y-beliekkel, ha az X csúcshalmaz kielégíti a Hall-feltételt.
A korábbi jelöléseket használva a Hall-feltétel: minden A részhalmazára X-nek igaz, hogy |Г(A)| |A|.
Logikai ekvivalenciák
szerkesztésEz a tétel tagja annak a 7 db különösen jelentős kombinatorikai tételnek, amelyek egyébként logikailag ekvivalensek. Ezek:
- Kőnig-tétel
- A Kőnig–Egerváry-tétel (1931) (Kőnig Dénes, Egerváry Jenő)
- Menger–tétel (1927)
- A Maximális folyam–minimális vágás-tétel (Ford-Fulkerson-algoritmus)
- A Birkhoff–Neumann-tétel (1946)
- Dilworth-tétel
Hivatkozások
szerkesztés- Equivalence of seven major theorems in combinatorics[halott link]
- Katona, Recski, Szabó: A számítástudomány alapjai. Typotex. Budapest, 2006. p. 58,59.
További információk
szerkesztés- Marriage Theorem a cut-the-knot honlapról
- Marriage Theorem and Algorithm a cut-the-knot honlapról
Ez a szócikk a PlanetMath proof of Hall's marriage theorem cikkéből származó szövegen alapul. A PlanetMath GFDL licenc alatt terjeszthető.