Hallova věta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Hallova věta je matematické tvrzení dokázané v roce 1935 anglickým matematikem Philipem Hallem. Týká se kombinatoriky a podává nutnou a postačující podmínku pro existenci systému různých reprezentantů ze systému podmnožin.

Znění[editovat | editovat zdroj]

Nechť S = {S1, S2, … } je (ne nutně spočetná) množina konečných podmnožin množiny M.

Systém různých reprezentantů (někdy se zkracuje na SRR) je množina X = {x1, x2, …} různých prvků množiny M (kde |X| = |S|), přičemž pro každé i platí, že xi je prvkem Si.

Hallova podmínka pro množinu S je splněna, pokud pro každou její podmnožinu T platí, že

|\bigcup T_i| \ge |T| (tj. libovolných n množin z množiny S má dohromady alespoň n prvků)

Hallova věta pak říká, že pro množinu S = {S1, S2, … } existuje SRR X = {x1, x2, … }, právě když S splňuje Hallovu podmínku.

Příklady[editovat | editovat zdroj]

Triviální[editovat | editovat zdroj]

(i) Je dán množinový systém M = (M_i : i \in I). Mějme množiny I = {1,2,3,4}, M1 = {a, b, d}, M2 = {a, c}, M3 = {b, c}, M4 = {b, d}. Existuje SRR?

Odpověď: Ano, SRR existuje, například v M1 vybereme b, v M2 vybereme a, v M3 vybereme c a v M4 zvolíme d.

(ii) Je dán množinový systém M = (M_i : i \in I). Mějme množiny I = {1,2,3,4}, M1 = {a, c}, M2 = {a, c}, M3 = {b, c}, M4 = {a, b}. Chceme rozhodnout, zda existuje SRR.

Řešení: SRR neexistuje, protože není splněna Hallova podmínka. Zvolíme-li totiž množinu J jako množinu indexů takovou, že J = {1,2,3,4}, pak by podle Hallovy věty mělo platit |\bigcup M_i| \ge |J|. To ale neplatí, protože |\bigcup M_i| = |{a,b,c}|= 3 a |J| = 4.

Sezdávací věta[editovat | editovat zdroj]

Historická formulace tohoto problému (díky které se v anglofonním prostředí Hallově větě občas říká také „marriage theorem“ a Hallově podmínce „marriage condition“) zní tak, že máme n mužů a n žen, přičemž ke každé ženě i muži máme přiřazenu množinu potenciálních partnerů a máme za úkol zjistit, jestli můžeme přiřadit každé ženě jednoho různého muže, aby byla všechna takto vytvořená partnerství v definovaných skupinách.

Toto zadání se od hledání SRR poněkud liší v tom, že se v něm na problém díváme jakoby z obou stran. Při hledání SRR bychom chtěli uspokojit buď jen ženy s jejich požadavky na muže nebo muže s jejich požadavky na ženy. Problémy jsou však převoditelné.

Využití[editovat | editovat zdroj]

Pomocí Hallovy věty lze dokázat, že

Důkaz věty[editovat | editovat zdroj]

Důkaz se provádí matematickou indukcí a patří do základních hodin kombinatoriky na vysokých školách.