Hallsova věta o manželství - Halls marriage theorem - Wikipedia

v matematika, Hallova věta o manželství, prokázáno Philip Hall  (1935 ), je věta se dvěma ekvivalentními formulacemi:

• The kombinační formulace se zabývá sbírkou konečný sady. Poskytuje nezbytnou a dostatečnou podmínku pro to, aby bylo možné vybrat z každé sady odlišný prvek.
• The teoretická graf formulace se zabývá a bipartitní graf. Dává nezbytnou a dostatečnou podmínku pro nalezení a vhodný který pokrývá alespoň jednu stranu grafu.

Kombinatorická formulace

Nechat ${ displaystyle S}$ být (možná nekonečný) rodina konečný podmnožiny z ${ displaystyle X}$, kde členové ${ displaystyle S}$ jsou počítáno s multiplicitou (To znamená, ${ displaystyle S}$ může obsahovat několikrát stejnou sadu).^[1]

A příčný pro ${ displaystyle S}$ je obraz z injekční funkce ${ displaystyle f}$ z ${ displaystyle S}$ na ${ displaystyle X}$ takhle ${ displaystyle f (s)}$ je prvek sady ${ displaystyle s}$ pro každého ${ displaystyle s}$ v rodině ${ displaystyle S}$. Jinými slovy, ${ displaystyle f}$ vybere jednoho zástupce z každé sady v ${ displaystyle S}$ takovým způsobem, že si dva z těchto zástupců nejsou rovni. Alternativní termín pro příčný je systém odlišných zástupců.

Sbírka S uspokojuje podmínka manželství kdy pro každou podrodinu ${ displaystyle W subseteq S}$,

${ displaystyle | W | leq { Bigl |} bigcup _ {A in W} A { Bigr |}.}$

Znovu vyjádřeno, podmínka manželství tvrdí, že každá podrodina ${ displaystyle S}$ obsahuje alespoň tolik odlišných členů, kolik je množin v podrodině.

Pokud podmínka manželství selže, nemůže existovat průřez ${ displaystyle f}$ z ${ displaystyle S}$.

Hallova věta říká, že platí také obrácená slova:

Příklady

příklad 1, podmínka manželství splněna

Příklad 1: Zvažte S = {A₁, A₂, A₃} s

A₁ = {1, 2, 3}

A₂ = {1, 4, 5}

A₃ = {3, 5}.

Platný příčný by byl (1, 4, 5). (Všimněte si, že to není jedinečné: (2, 1, 3) například funguje stejně dobře.)

příklad 2, porušena podmínka manželství

Příklad 2: Zvažte S = {A₁, A₂, A₃, A₄} s

A₁ = {2, 3, 4, 5}

A₂ = {4, 5}

A₃ = {5}

A₄ = {4}.

Žádný platný příčný neexistuje; podmínka manželství je porušena, jak ukazuje podrodina Ž = {A₂, A₃, A₄}. Zde je počet sad v podrodině |Ž| = 3, zatímco sjednocení tří množin A₂ U A₃ U A₄ obsahuje pouze 2 prvky X.

Příklad 3: Zvažte S = {A₁, A₂, A₃, A₄} s

A₁ = {A, b, C}

A₂ = {b, d}

A₃ = {A, b, d}

A₄ = {b, d}.

Jediné platné průřezy jsou (C, b, A, d) a (C, d, A, b).

Žádost o manželství

Standardní příklad aplikace manželské věty je představit si dvě skupiny; jeden z n muži a jeden z n ženy. Pro každou ženu existuje podmnožina mužů, z nichž by se šťastně provdala; a každý muž by se rád oženil se ženou, která si ho chce vzít. Zvažte, zda je možné spárovat (v manželství ) muže a ženy, aby byl každý člověk šťastný.

Pokud to necháme A_i být souborem lidí, které i-tá žena by se ráda provdala, pak věta o manželství uvádí, že každá žena se může šťastně provdat za muže tehdy a jen tehdy, pokud je kolekce sadA_i} splňuje podmínku manželství.

Všimněte si, že podmínkou manželství je to pro každou podmnožinu ${ displaystyle I}$ žen, počet mužů, které by si alespoň jedna ze žen s radostí vzala, ${ displaystyle | bigcup _ {i in I} A_ {i} |}$být alespoň tak velký jako počet žen v této podskupině, ${ displaystyle | I |}$. Je zřejmé, že tento stav je nutné, jako by to nedrželo, není dost mužů na sdílení mezi ${ displaystyle I}$ ženy. Zajímavé je, že je to také a dostatečný stav.

Teoretická formulace grafu

modré hrany představují shodu

Nechat G být konečný bipartitní graf s bipartitními sadami X a Y (tj. G := (X + Y, E)). An X-perfektní shoda (také zvaný: X-saturující shoda) je vhodný který pokrývá každý vrchol v X.

Pro podmnožinu Ž z X, nechť N_G(Ž) označují sousedství z Ž v G, tj. množina všech vrcholů v Y přilehlý na nějaký prvek Ž. Veta o manželství v této formulaci uvádí, že existuje X- perfektní shoda kdyby a jen kdyby pro každou podmnožinu Ž z X:

${ displaystyle | W | leq | N_ {G} (W) |.}$

Jinými slovy: každá podmnožina Ž z X má dostatečně mnoho sousedních vrcholů v Y.

Důkaz teoretické verze grafu

Snadný směr: předpokládáme, že nějaké shody M nasycuje každý vrchol X, a dokázat, že Hallův stav je pro všechny uspokojený Ž ⊆ X. Nechat M(Ž) označuje množinu všech vrcholů v Y uzavřeno M k danému Ž. Podle definice shody |M(Ž)| = |Ž |. Ale M(Ž) ⊆ N_G(Ž), protože všechny prvky M(Ž) jsou sousedé Ž. Takže, | N_G(Ž)| ≥ |M(Ž) | a tedy | N_G(Ž)| ≥ |Ž|.

Tvrdý směr: předpokládáme, že neexistuje X- perfektní shoda a prokázat, že Hallova podmínka je porušena alespoň u jednoho Ž ⊆ X. Nechat M být maximální shoda a u vrchol není nasycen M. Zvažte vše střídavé cesty (tj. cesty dovnitř G střídavě s použitím hran venku a uvnitř M) začínající od u. Nechte soubor všech bodů dovnitř Y připojeno k u těmito střídavými cestami Za množina všech bodů v X připojeno k u těmito střídavými cestami (včetně u sám) být Ž. Žádná maximální střídavá cesta nemůže skončit vrcholem v Y, aby to nebylo rozšiřující cesta, abychom mohli rozšířit M na přísně větší shodu přepnutím stavu (patří do M nebo ne) všech okrajů cesty. Tedy každý vrchol dovnitř Z je uzavřeno M na vrchol v Ž \ {u}. Naopak každý vrchol proti v Ž \ {u} odpovídá M na vrchol v Z (jmenovitě vrchol předcházející proti na střídavé cestě končící v proti). Tím pádem, M poskytuje rozpor s Ž \ {u} a Z, což znamená |Ž| = |Z| + 1. Na druhé straně N_G(Ž) ⊆ Z: nechte proti v Y být připojen k vrcholu w v Ž. Hrana (w,proti) musí být v M, v opačném případě u dosáhne w střídavou cestou, která neobsahuje protia mohli bychom se vydat touto střídavou cestou končící na w a rozšířit ji pomocí proti, získání rozšiřující se cesty (což by opět bylo v rozporu s maximálností M). Proto proti musí být v Z, a tak | N_G(Ž)| ≤ |Z| = |Ž| − 1 < |Ž|.

Konstruktivní důkaz tvrdého směru

Definovat a Hall porušovatel jako podmnožina Ž z X pro které | N_G(Ž)| < |Ž|. Li Ž je porušovatel Hall, pak neexistuje žádná shoda, která by nasycovala všechny vrcholy Ž. Proto také neexistuje žádná shoda, která by nasycovala X. Hallova manželská věta říká, že graf obsahuje X-dokonalé přizpůsobení, pokud a pouze pokud neobsahuje žádné narušitele Hall. Následující algoritmus dokazuje tvrdý směr věty: najde buď X- perfektní shoda nebo Hallův porušovatel. Používá jako podprogram algoritmus, který je vzhledem k shodě M a bezkonkurenční vrchol X₀, buď najde M-augmentační cesta nebo Hallův porušovatel obsahující X₀.

Využívá to

1. Inicializovat M : = {}. // Prázdná shoda.
2. Tvrdit: M je odpovídající v G.
3. Li M nasycuje všechny vrcholy X, pak vrátit X- perfektní shoda M.
4. Nechat X₀ být nepřekonatelným vrcholem (vrchol v X V (M)).
5. Za použití Hall porušovatel algoritmus, najděte buď Hallova narušitele, nebo M-augmentační cesta.
6. V prvním případě vrátit porušovatele Hall.
7. V druhém případě použijte M-augmenting cesta ke zvětšení velikosti M (o jeden okraj) a vraťte se ke kroku 2.

Při každé iteraci M roste o jednu hranu. Tento algoritmus proto musí skončit maximálně |E| iterace. Každá iterace trvá maximálně |X| čas. Celková složitost za běhu je podobná metodě Ford-Fulkerson pro hledání a maximální shoda mohutnosti.

Ekvivalence kombinatorické formulace a grafově teoretické formulace

Nechat S = (A₁, A₂, ..., A_n) Kde A_i jsou konečné množiny, které se nemusí odlišovat. Nechte set X = {A₁, A₂, ..., A_n} (tj. množina jmen prvků prvku S) a sada Y být spojením všech prvků ve všech A_i.

Tvoříme konečnou bipartitní graf G := (X + Y, E), s bipartitními sadami X a Y připojením libovolného prvku do Y ke každému A_i jehož je členem. Příčný z S je X-perfektní vhodný (shoda, která pokrývá každý vrchol v X) bipartitního grafu G. Problém v kombinatorické formulaci lze tedy snadno přeložit na problém v grafově-teoretické formulaci.

Topologický důkaz

Hallova věta může být prokázána (nekonstruktivně) na základě Spernerovo lemma.^{[2]:Thm.4.1,4.2}

Aplikace

Věta má mnoho dalších zajímavých „nemanželských“ aplikací. Vezměte například a standardní balíček karet a rozdělit je na 13 hromádek po 4 kartách. Pak pomocí věty o manželství můžeme ukázat, že je vždy možné vybrat přesně 1 kartu z každé hromádky, takže 13 vybraných karet obsahuje přesně jednu kartu každé hodnosti (eso, 2, 3, ..., královna, Král).

Více abstraktně, pojďme G být skupina, a H být konečný podskupina z G. Potom lze z manželské věty ukázat, že existuje množina T takhle T je příčný pro obě sady vlevo kosety a správné kosety H v G.

Věta o manželství se používá v obvyklých důkazech o tom, že (r × n) Latinský obdélník lze vždy rozšířit na ((r +1) × n) Latinský obdélník, když r < n, a tak nakonec k Latinský čtverec.

Logické ekvivalence

Tato věta je součástí sbírky pozoruhodně silných vět v kombinatorice, které všechny spolu souvisejí v neformálním smyslu v tom smyslu, že je jednodušší dokázat jednu z těchto vět z jiné než z prvních principů. Tyto zahrnují:

• The König – Egerváryho věta (1931) (Dénes Kőnig, Jenő Egerváry )
• Königova věta^[3]
• Mengerova věta (1927)
• The věta o maximálním toku o minimálním řezu (Ford-Fulkersonův algoritmus)
• The Birkhoff – Von Neumannova věta (1946)
• Dilworthova věta.

Zejména,^[4][5] existují jednoduché důkazy o implikacích Dilworthova věta ⇔ Hallova věta ⇔ König – Egerváryova věta ⇔ Königova věta.

Nekonečné rodiny

Varianta Marshall Hall Jr.

Zkoumáním Philip Hall originální důkaz pečlivě, Marshall Hall, Jr. (žádný vztah k Philipu Hallovi) dokázal vyladit výsledek způsobem, který dovolil důkazu pracovat nekonečně S.^[6] Tato varianta upřesňuje teorém o manželství a poskytuje dolní mez počtu transverzálů, které daný S mohou mít. Tato varianta je:^[7]

Předpokládejme, že (A₁, A₂, ..., A_n), Kde A_i jsou konečné množiny, které se nemusí odlišovat, jde o rodinu množin, které splňují podmínku manželství, a předpokládejme | |A_i| ≥ r pro i = 1, ..., n. Pak je počet různých průřezů pro rodinu alespoň r! -li r ≤ n a r(r − 1) ... (r − n + 1) pokud r > n.

Připomeňme, že příčné pro rodinu S je uspořádaná sekvence, takže dva různé příčné směry mohou mít přesně stejné prvky. Například rodina A₁ = {1, 2, 3}, A₂ = {1, 2, 5} má obě (1, 2) a (2, 1) jako odlišné příčné.

Stav manželství se nerozšiřuje

Následující příklad, kvůli Marshall Hall, Jr., ukazuje, že podmínka manželství nezaručuje existenci příčného v nekonečné rodině, ve které jsou povoleny nekonečné množiny.

Nechat S být rodinou, A₀ = {1, 2, 3, ...}, A₁ = {1}, A₂ = {2}, ..., A_i = {i }, ...

Podmínka manželství platí pro tuto nekonečnou rodinu, ale nelze vytvořit žádný příčný.^[8]

Obecnější problém výběru (ne nutně odlišného) prvku z každé kolekce neprázdný sady (bez omezení, pokud jde o počet sad nebo velikost sad), jsou obecně povoleny, pouze pokud axiom volby je přijat.

Věta o manželství se vztahuje na nekonečný případ, je-li to uvedeno správně. Vzhledem k bipartitnímu grafu se stranami A a B, říkáme, že podmnožina C z B je menší nebo stejné velikosti jako podmnožina D z A v grafu pokud v grafu existuje injekce (konkrétně pouze s použitím okrajů grafu) z C na D, a že je v grafu přísně menší, pokud navíc není v grafu žádná injekce v opačném směru. Všimněte si, že vynechání v grafu poskytuje běžnou představu o srovnání kardinálností. Věta o nekonečném manželství uvádí, že existuje injekce z A na B v grafu, pokud a pouze v případě, že neexistuje žádná podmnožina C z A takhle N(C) je přísně menší než C v grafu.^[9]

Frakční shoda varianta

A zlomková shoda v grafu je přiřazení nezáporných vah každé hraně, takže součet vah sousedících s každým vrcholem je nanejvýš 1. Frakční shoda je X-perfektní, pokud je součet vah sousedících s každým vrcholem přesně 1. Následující jsou ekvivalentní pro bipartitní graf G = (X + Y, E.):^[10]

• G připouští X-perfektní shodu.
• G připouští X-perfektní zlomkovou shodu. Důsledek je zřejmý, protože X-perfect matching je speciální případ X-perfektní zlomková shoda, ve které je každá váha buď 1 (pokud je hrana ve shodě), nebo 0 (pokud není).
• G splňuje Hallův stav manželství. Důsledek platí, protože pro každou podmnožinu Ž z X, součet hmotností poblíž vrcholů Ž je |Ž|, takže hrany sousedící s nimi nutně sousedí alespoň s | W | vrcholy Y.

Kvantitativní varianta

Když Hallova podmínka neplatí, původní věta nám říká pouze to, že dokonalá shoda neexistuje, ale neříká nám největší shodu, která existuje. Abychom se tyto informace dozvěděli, potřebujeme pojem nedostatek grafu. Vzhledem k bipartitnímu grafu G = (X + Y, E.), nedostatek G w.r.t. X je maximum ve všech podskupinách Ž z Xrozdílu | Ž| - | N_G(Ž) |. Čím větší je nedostatek, tím dále je graf od uspokojení Hallova stavu.

Pomocí Hallovy manželské věty lze dokázat, že pokud jde o nedostatek bipartitního grafu G je d, pak G připouští shodu velikosti alespoň |X| -d. Vidět Nedostatek (teorie grafů) pro důkaz.

Zobecnění

• Zobecnění Hallova věta na obecné grafy (které nemusí být nutně bipartitní) poskytuje Tutteova věta.
• Zevšeobecnění Hallovy věty na bipartitní hypergrafy je poskytována různými Hallovy věty pro hypergrafy.

Poznámky

Reference

• Brualdi, Richard A. (2010), Úvodní kombinatorika, Horní sedlo, NJ: Prentice-Hall / Pearson, ISBN  978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge: Cambridge University Press, ISBN  978-0-521-45761-3
• Dongchen, Jiang; Nipkow, Tobias (2010), "Hall's Marriage Theorem", Archiv formálních důkazů, ISSN  2150-914X. Počítačem ověřený důkaz.
• Hall, Jr., Marshall (1986), Kombinatorická teorie (2. vyd.), New York: John Wiley & Sons, ISBN  978-0-471-09138-7
• Hall, Philip (1935), „O zástupcích podskupin“, J. London Math. Soc., 10 (1): 26–30, doi:10.1112 / jlms / s1-10.37.26
• Halmos, Paul R.; Vaughan, Herbert E. (1950), „Manželský problém“, American Journal of Mathematics, 72 (1): 214–215, doi:10.2307/2372148, JSTOR  2372148, PAN  0033330
• Reichmeider, P.F. (1984), Ekvivalence některých kombinačních shodných vět, Polygonální nakladatelství, ISBN  978-0-936428-09-3
• Roberts, Fred S .; Tesman, Barry (2009), Aplikovaná kombinatorika (2. vyd.), Boca Raton: CRC Press, ISBN  978-1-4200-9982-9
• van Lint, J. H .; Wilson, R.M. (1992), Kurz kombinatoriky, Cambridge: Cambridge University Press, ISBN  978-0-521-42260-4

externí odkazy

• Věta o manželství na cut-the-uzel
• Věta o manželství a algoritmus na cut-the-uzel
• Hallova věta o manželství byla vysvětlena intuitivně na Luckyho poznámky.

Tento článek včlení materiál z důkazu o Hallově manželské větě PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.