Hall-tétel

A Wikipédiából, a szabad enciklopédiából

A matematikában a Hall-tétel (1935, Philip Hall), egy kombinatorikai eredmény, 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:

|\bigcup T_i| \ge |T| (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: 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 I részhalmazára a nőknek, azon férfiak száma, akik az I-beli nők közül legalább egyet elvennének (\scriptstyle{|\bigcup\limits_{i\in I} T_i|}) legyen legalább akkora, mint a nők ezen részhalmazának elemszáma, \scriptstyle |I| = |\{T_i: i \in I\}| . Az természetes, hogy a feltétel szükséges, hiszen enélkül nem lenne elég az I-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és | forrásszöveg szerkesztése]

A Hall-tétel véges esetét fogjuk az |S|-re, azaz S 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  \left\vert\cup T\right\vert \ge \left\vert T\right\vert+1 erősebb feltételt tesszük fel minden \emptyset \ne T \subset S-re. Vegyük bármely x\in S_n -et is S_n reprezentánsának; a DRR-t  S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\} -ből kell választanunk. De, ha  \{S_{j_1}\setminus\{x\},...,S_{j_k}\setminus\{x\}\} = T'\subseteq S' , akkor a feltevésünk szerint  \left\vert\cup T'\right\vert \ge \left\vert\cup_{i=1}^{k} S_{j_i}\right\vert-1 \ge k. A tétel már bizonyított esetét S'-re alkalmazva látható, hogy találhatunk megfelelő DRR-t S'-höz.

Egyébként bizonyos \emptyset\ne T \subset S értékekre az éles egyenlőség áll fent  \left\vert\cup T\right\vert=\left\vert T\right\vert. T-n belül már bármely T'\subseteq T\subset S-re beláttuk  \left\vert\cup T'\right\vert\ge\left\vert T'\right\vert-t, így a tétel már bizonyított esete alapján választhatunk DRR-t T számára. Az maradt hátra, hogy találjunk egy DRR-t S\setminus T-hez, ami nélkülözi \cup T összes elemét (ezek az elemek T 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 T'\subseteq S\setminus T-re, \cup T elemeinek figyelembe vétele nélkül is marad elég elem \cup T'-ben: azaz  \left\vert\cup T' \setminus \cup T\right\vert \ge \left\vert T'\right\vert-t kell belátnunk.

De

\left\vert\cup T' \setminus \cup T\right\vert

 = \left\vert\bigcup(T\cup T')\right\vert - \left\vert\cup T\right\vert \ge \left\vert T\cup T'\right\vert - \left\vert T\right\vert

 = \left\vert T\right\vert + \left\vert T'\right\vert - \left\vert T\right\vert = \left\vert T'\right\vert,

T és T' diszjunktságát felhasználva. Így a tétel már bizonyított esetét felhasználva látható, hogy S\setminus T-hez tényleg létezik megfelelő DRR, amely \cup T egyetlen elemét sem tartalmazza.

Ezzel bebizonyítottuk a tételt.

Következmény[szerkesztés | forrásszöveg szerkesztése]

Ha G(V_1, V_2, E) egy páros gráf, akkor G-ben akkor és csak akkor van V_1-et lefedő párosítás, ha \vert S\vert\leq \vert N(S)\vert minden S\subset V_1 részhalmazra.

Gráfelmélet[szerkesztés | forrásszöveg szerkesztése]

A 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-el é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:

Példa egy páros gráfra, ahol a fenti ponthalmaz teljesíti a Hall-feltételt, így létezik őt lefedő párosítás.

Jelentse N_G(X) 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

\|X\| \leq \|N_G(X)\|

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és | forrásszöveg szerkesztése]

Legyen 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)|  \ge |A|.

Logikai ekvivalenciák[szerkesztés | forrásszöveg szerkesztése]

Ez a tétel tagja annak a 7 db különösen jelentős kombinatorikai tételnek, amelyek egyébként logikailag ekvivalensek. Ezek:

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]

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ő.