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á.
Hallova veta
-
- 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
Tady je to vysvetlene: http://kam.mff.cuni.cz/~valla/kg.html
- lukax
- Matfyz(ák|ačka) level I
- Příspěvky: 45
- Registrován: 12. 1. 2009 11:32
- Typ studia: Informatika Bc.
- Login do SIS: 62666361
Re: Hallova veta
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](http://www.texify.com/img/%5CLARGE%5C%21%5Cforall%20I%20%5Csubseteq%20%5C%7B1..n%5C%7D%3A%20%5Cleft%7CI%5Cright%7C%20%5Cleq%20%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_i%5Cright%7C.gif)
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](http://www.texify.com/img/%5CLARGE%5C%21%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_K%5E%27_i%5Cright%7C%3D%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_K_i%5Cright%7C-%5Cleft%7C%5Ccup_%7Bi%5Cin%20J%7DM_J_i%5Cright%7C%5Cgeq%20%5Cleft%7CI%5Ccup%20J%5Cright%7C-%5Cleft%7CJ%5Cright%7C%3D%5Cleft%7CI%5Cright%7C.gif)
(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](http://www.texify.com/img/%5CLARGE%5C%21%5Cleft%7CI%5Cright%7C%20%5Cleq%20%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_i%5Cright%7C-1%20%5Cleq%20%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7D%7BM%27_i%7D%5Cright%7C.gif)
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.
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](http://www.texify.com/img/%5CLARGE%5C%21%5Cforall%20I%20%5Csubseteq%20%5C%7B1..n%5C%7D%3A%20%5Cleft%7CI%5Cright%7C%20%5Cleq%20%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_i%5Cright%7C.gif)
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](http://www.texify.com/img/%5CLARGE%5C%21%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_K%5E%27_i%5Cright%7C%3D%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_K_i%5Cright%7C-%5Cleft%7C%5Ccup_%7Bi%5Cin%20J%7DM_J_i%5Cright%7C%5Cgeq%20%5Cleft%7CI%5Ccup%20J%5Cright%7C-%5Cleft%7CJ%5Cright%7C%3D%5Cleft%7CI%5Cright%7C.gif)
(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](http://www.texify.com/img/%5CLARGE%5C%21%5Cleft%7CI%5Cright%7C%20%5Cleq%20%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7DM_i%5Cright%7C-1%20%5Cleq%20%5Cleft%7C%5Ccup_%7Bi%5Cin%20I%7D%7BM%27_i%7D%5Cright%7C.gif)
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.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 18
- Registrován: 2. 2. 2009 21:53
- Typ studia: Informatika Bc.
Re: Hallova veta
Diky moc, je to takovej zmatenej dukaz, docela jsi mi ho osvetlil ![Smile :-)](./images/smilies/icon_smile.gif)
![Smile :-)](./images/smilies/icon_smile.gif)