Hallova veta

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Hallova veta

Příspěvek od marion »

Zdravím,
nevíte někdo o nějakém dobrém materiálu, kde je vysvětlený důkaz Hallovy věty? V Kapitolách není, a tomu důkazu v poznámkách nerozumím. Případně kdyby se to tu někdo pokusil lidsky napsat, budu moc vděčná.
dobry_den
Matfyz(ák|ačka) level I
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Hallova veta

Příspěvek od dobry_den »

Uživatelský avatar
lukax
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 12. 1. 2009 11:32
Typ studia: Informatika Bc.

Re: Hallova veta

Příspěvek od lukax »

V těch skriptíčkách je to dělané jinak, než jsme měli na přednášce. Zkusím převyprávět, jak bych to Pangrácovi pověděl já, potřebuju si to zopakovat:

Hallova věta: Množinový systém M má systém různých reprezentantů právě tehdy, splňuje-li Hallovu podmínku.

Hallova podmínka: Pro každou indexovou podmnožinu {1..n} je velikost této podmnožiny menší či rovna než velikost sjednocení přes množiny z M určené touto indexovou množinou. Tedy:

Obrázek

Výklad: Mějme n holek, každá z nich pokukuje po nějaké množině kluků. Když vezmeme těchhle n množin a dáme je dohromady, máme množinový systém M. SRR je zpárování každé holky k nějakému různému klukovi. Hallova podmínka říká, že vybereme-li libovolných k holek a hodíme do pytle všechny kluky, kteří přijdou pěkní alespoň jedné z vybraných k holek, bude v pytli alespoň k kluků. ;-)

Důkaz Hallovy věty:

Existence SRR implikuje Hallovu podmínku: To je jasné: mějme nalezený systém různých reprezentantů. To nám každé množiny z M dává jeden její prvek a toto přiřazení je prosté. Proto když vybereme z M libovolných k množin, dostaneme od nalezeného SRR k různých prvků-reprezentantů, od každé množiny jednoho. Přitom těchto k prvků náleží vždy alespoň jedné z k množin, proto patří do sjednocení v Hallově podmínce a proto její nerovnost jistě platí: je tam nyní, že k je menší nebo rovno k (máme ze SRR) + možná nějaké další množiny (kluci bez takto oindexovaných holek).

Hallova podmínka implikuje existenci SRR: To je tak trošku větší zázrak matičky přírody než výše popisované romantické pletení. :-) Dělá se to matematickou indukcí.

k nechť je součet velikostí všech množin v M. (Ne velikost sjednocení, ta je potenciálně menší!) Indukci povedeme podle tohoto k.

1. zvláštní případ

Ať existuje indexová množina J, neprázdná vlastní podmnožina z {1..n}, jejíž velikost je rovna velikosti sjednocení přes jí oindexované množiny z M.

Roztřískněme M na MJ a MK: v MJ budou množiny oindexované J, v MK všechny ostatní (v K budiž jejich indexy). O MJ víme, že splňuje Hallovu podmínku, vždyť M splňuje Hallovu podmínku.

Všimli jsme si už, že žádná množina z M není prázdná? Jestli ne, všimněme si toho teď! Vždyť kdyby byla i-tá množina z M prázdná, neplatila by jistě Hallova podmínka pro I={i} (1<0). Proto jistě platí, že součet velikostí MJ je menší než k. (V MK něco bylo, nerovnost je ostrá.)

To bylo důležité proto, abych věděli, že se v indukci odvoláváme na menší případ, ne sami na sebe. Takže nám z ní vypadává, že MJ má SRR.

Teď si uděláme MK' takto: od každé množiny MK množinově odebereme sjednocení přes všechny prvky v MJ. Těch je jeden a víc, proto je součet velikostí množin v MK' menší než k a můžeme aplikovat indukci… Pokud ovšem pro takto modifikovaný množinový systém stále platí Hallova podmínka! Inu, ověříme ji: I je libovolná indexová podmnožina pro MK, tedy I je podmnožina K, potom:

Obrázek

(I a J jsou disjunktní, proto platí ta poslední rovnost. Disjunktnost je vidět z toho, že I je podmnožina K, která je doplňkem J do {1..n}.)

Hallova podmínka pro MK' platí, umíme pro něj tedy z indukce najít SRR, ten bude určitě fungovat i na MK, protože ten má akorát nějaké prvky navíc. Zároveň máme SRR pro MJ, ale ten má určitě jiné prvky než ten na MK, protože jsme při hledání K-čkového odsekli všechny prvky z J-éčkově indexovaných množin. Proto máme SRR i pro celou M: pro prvky z indexové množiny J vezmeme ty reprezentanty, které se nám vrátili z jedné indukce, pro prvky z indexové množiny K vezmeme ty z druhé indukce.

Bohužel byly naše předpoklady… odvážné. Tento případ byl docela speciální: určitě nemusíme najít takovou indexovou množinu J, která bude mít přesně stejnou velikost jako je velikost sjednocení jí indexovaných množin M.

Práce to však nebyla marná.

2. zvláštní případ

Řekněme, že existuje prvek, který se vyskytuje pouze v jedné množině m našeho M. Pokud máme vytvořit SRR, nezbývá nám ho než vybrat jako reprezentanta pro tuto svoji množinu m. Nechť je M' množinový systém jako je M, akorát bez množiny m.

Pro M' jistě platí Hallova podmínka, protože platí pro M. Zároveň je suma přes velikosti množin v M' menší než k, aspoň o jednotku, vždyť jsme odebrali m. Můžeme tedy snadno použít indukci a Hallova věta pro tento případ také platí.

Pokud nenastal ani jeden výše zmiňovaný případ, přistupme ke konečné zteči.

x je libovolný prvek Mn. M' budiž množinový systém jako M, jen bez tohoto x ve své n-té množině (jinde x v poklidu setrvává). M' je menší než M a budeme na ni moci pustit indukci, až ověříme, že splňuje Hallovu podmínku. Dostáváme proto opět a naposled k ověření libovolnou indexovou množinu I z {1..n}.

Jelikož nenastal první případ (kde je rovnost), velikost I je ostře menší než velikost sjednocení množin z M. Proto můžeme psát:

Obrázek

Teď pozor: je to všechno? Pocitvý čtenáři, jestlipak jsi na počátku rozboru prvního případu dobře zvážil důležitost toho, že vybíráme pouze vlastní indexovou podmnožinu? Bylo to potřeba, jinak bychom nemohli indukovat. Jenže naše nynější ověření potřebuje zvládnout i tento případ, kdy I={1..n}, tedy se ptáme, jestli je velikost sjednocení přes všechny množiny v M větší rovna n.

To je, protože nenastal druhý případ a každý prvek tu byl zastoupen minimálně dvakrát: tedy tím, že jsme libovolný odebrali, nezmenšili jsme jejich počet a pokud předtím tato specialita Hallovy podmínky platila, platí i nyní!

To jsme chtěli ukázat.
vexis
Matfyz(ák|ačka) level I
Příspěvky: 18
Registrován: 2. 2. 2009 21:53
Typ studia: Informatika Bc.

Re: Hallova veta

Příspěvek od vexis »

Diky moc, je to takovej zmatenej dukaz, docela jsi mi ho osvetlil :-)
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“