The Postal Owl

2. Hallova věta: m má SRR $\iff \forall J \subseteq I: |J| \leq |\bigcup_{j \in J} M_j$ Převedeme si množinový systém na bipartitní graf s partitami X a I jako na přednášce. * $\implies$ Množinový systém má $SRR \implies$ $\forall J \subseteq I: \exists$ párování velikosti $|J| \implies$ Minimální vrcholové pokrytí má velikost $|J|$. Neexistuje menší vrcholové pokrytí. Tvrzení: Sjednocení $\bigcup_{i \in I} M_i$ má velikost alespoň $|J|$. Důkaz: Kdyby mělo menší velikost, nalezli bychom menší vrcholové pokrytí, stačilo by vybrat všechny vrcholy sjednocení a protože se jedná o bipartitní graf, vybráním všech těchto vrcholů bychom pokryli i všechny hrany. Protože ale velikost minimálního pokrytí je daná, toto nelze najít. Toto tvrzení odpovídá pravé straně Hallovy podmínky, tedy $\square$ * Lemma A: Pro každé $j \in J$, alespoň jedna hrana vede do sjednocení, jinak by množina byla prázdná a pro $J^\prime = \{ j \}$ by $1 = |J^\prime| > |\bigcup_{j \in J^\prime} M_j| = |M_j| = 0$ $\square$ * $\impliedby$ $\forall J \subseteq I: |J| \leq |\bigcup_{j \in J} M_j| \implies$ Minimální vrcholové pokrytí má velikost alespoň J (právě J, protože stačí vybrat J, ale to neřešíme) Dk: Sporem: Uvažme menší vrcholové pokrytí G, $|G| < |J|$. Pak uvažme množinu $B = G \cap \bigcup_{i\in I} M_i$. Tento průnik je určitě neprázdný, protože jinak bychom v pokrytí vybrali pouze vrcholy z $J$, alespoň jeden vrchol z J by zůstal nepokryt. A hrana vedoucí z něj (dle lemmatu A existuje) by byla také nepokryta. Dále se podívejme na $J^\prime = J \setminus G$. Všechny hrany z $l \in J^\prime$ musí vést do $B$, jinak by nebyly pokryty vrcholovým pokrytím (nebyly by pokryty ani v partitě sjednocení, ani v partitě J). Ale z podmínky platí $|B| \geq |J^\prime|$ No ale v tom případě $|G| = |B| + |J \cap G| \geq |J^\prime| + |J \cap G| = |J|$. (Poslední rovnost dostaneme z toho, že $J \cap G$ a $J^\prime = J \setminus G$ jsou disjunktní) Tedy $|G| \geq |J|$, to je spor s tím, že máme menší minimální pokrytí než $|J|$ Tak tedy máme z podmínky zaručeno, že $\forall J \subseteq I$ minimální pokrytí má velikost $|J|$, takže pro $I$ má minimální pokrytí velikost $|I|$, to odpovídá (maximálnímu) párování o velikosti $|I|$ a to už triviálně dává SRR.

Preview