Twierdzenie Halla o małżeństwie - Hall's marriage theorem

W matematyce , Halla małżeństwo twierdzenie , udowodnione przez Philip Hall  ( 1935 ), jest twierdzeniem z dwóch równoważnych preparatów:

• Kombinatoryczne preparat zajmuje zbiór skończonych zestawów . Daje konieczny i wystarczający warunek, aby móc wybrać odrębny element z każdego zestawu.
• W wykresie teoretyczne oferty formulacji z dwuczęściowego wykresie . Daje warunek konieczny i wystarczający do znalezienia dopasowania, które obejmuje przynajmniej jedną stronę wykresu.

Formuła kombinatoryczna

Pozwolić być (prawdopodobnie nieskończone) rodzina skończonych podzbiorów o , w których członkowie są liczone z wielości (czyli mogą zawierać ten sam zestaw kilka razy). ${\displaystyle S}$${\ Displaystyle X}$${\displaystyle S}$${\displaystyle S}$

Poprzeczny przez to obraz o injective zależności od celu , tak że jest elementem zestawu dla każdego z rodziny . Innymi słowy, wybiera jednego reprezentanta z każdego zestawu w taki sposób, że żadne dwa z tych reprezentantów nie są sobie równe. Alternatywnym terminem dla przekrojowych jest system odrębnych przedstawicieli . ${\displaystyle S}$ ${\displaystyle f}$${\displaystyle S}$${\ Displaystyle X}$${\displaystyle f(s)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle S}$${\displaystyle f}$${\displaystyle S}$

Zbiór S spełnia warunek małżeństwa, gdy dla każdej podrodziny , ${\displaystyle W\subseteq S}$

${\ Displaystyle | W | \ Leq {\ Bigl |} \ Bigcup _ {A \ w W} A {\ Bigr |}.}$

Ujmując to słowami, warunek małżeństwa zakłada, że ​​każda podrodzina zawiera co najmniej tylu odrębnych członków, ile jest zbiorów w podrodzinie. ${\displaystyle S}$

Jeśli warunek nie wtedy małżeństwo nie może być poprzeczna od . ${\displaystyle f}$${\displaystyle S}$

Twierdzenie Halla mówi, że odwrotność jest również prawdziwa:

Przykłady

Przykład 1: Rozważ S = { A ₁ , A ₂ , A ₃ } z

A ₁ = {1, 2, 3}

A ₂ = {1, 4, 5}

A ₃ = {3, 5}.

Prawidłowym przekrojem byłby (1, 4, 5). (Zauważ, że nie jest to wyjątkowe: na przykład (2, 1, 3) działa równie dobrze.)

Przykład 2: Rozważ S = { A ₁ , A ₂ , A ₃ , A ₄ } z

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

A ₂ = {4, 5}

A ₃ = {5}

A ₄ = {4}.

Nie istnieje żaden ważny przekroj; warunek małżeństwa jest naruszony, jak pokazuje podrodzina W = { A ₂ , A ₃ , A ₄ }. Tutaj liczba zbiorów w podrodzinie wynosi | W | = 3, podczas gdy suma trzech zbiorów A ₂ U A ₃ U A ₄ zawiera tylko 2 elementy X .

Przykład 3: Rozważ S = { A ₁ , A ₂ , A ₃ , A ₄ } z

A ₁ = { a , b , c }

A ₂ = { b , d }

A ₃ = { a , b , d }

A ₄ = { b , d }.

Jedynymi poprawnymi przekrojami są ( c , b , a , d ) i ( c , d , a , b ).

Wniosek o zawarcie małżeństwa

Standardowym przykładem zastosowania twierdzenia o małżeństwie jest wyobrażenie sobie dwóch grup; jeden z n mężczyzn i jeden z n kobiet. Na każdą kobietę przypada podgrupa mężczyzn, z których każdy z radością poślubi; i każdy mężczyzna byłby szczęśliwy, gdyby poślubił kobietę, która chce go poślubić. Zastanów się, czy możliwe jest połączenie (w małżeństwie ) mężczyzny i kobiety tak, aby każda osoba była szczęśliwa.

Jeśli pozwolimy, aby A _i było zbiorem mężczyzn, których i-ta kobieta byłaby szczęśliwa poślubić, wtedy twierdzenie o małżeństwie mówi, że każda kobieta może szczęśliwie poślubić wyjątkowego mężczyznę wtedy i tylko wtedy, gdy dla dowolnego podzbioru kobiet liczba mężczyźni, których przynajmniej jedna z tych kobiet chętnie poślubiłaby, , jest co najmniej tak duża, jak liczba kobiet w tym podzbiorze, . ${\ Displaystyle I}$${\ Displaystyle | \ bigcup _ {i \ w I} A_ {i} |}$${\displaystyle |ja|}$

Ten warunek jest konieczny , jak gdyby nie był spełniony, nie ma wystarczającej liczby mężczyzn do podziału wśród kobiet. Co ciekawe, jest to również warunek wystarczający . ${\displaystyle |ja|}$

Graficzna formuła teoretyczna

Niech G będzie skończonym grafem dwudzielnym ze zbiorami dwudzielnymi X i Y (tj. G  := ( X  + Y , E )). X-idealne dopasowanie (zwane również: X-nasycając dopasowanie ) jest dopasowanie która obejmuje każdy wierzchołek w X .  

W przypadku niektórych W z X , niech N _G ( W ) oznacza sąsiedztwie o W w G , to znaczy zestawu wszystkich wierzchołków Y przylegających do pewnego elementu W . Twierdzenie o małżeństwie w tym sformułowaniu mówi, że istnieje X -doskonałe dopasowanie wtedy i tylko wtedy, gdy dla każdego podzbioru W od X :

${\ Displaystyle | W | \ leq | N_ {G} (W) |.}$

Innymi słowy: każdy podzbiór W z X ma wystarczająco dużo sąsiednich wierzchołków w Y .

Dowód wersji teoretycznej grafów

Łatwy kierunek : zakładamy, że pewne pasujące M nasyca każdy wierzchołek X , i dowodzimy, że warunek Halla jest spełniony dla wszystkich W ⊆ X . Niech K ( W ) oznacza zbiór wszystkich wierzchołków Y równoważonych M do danej W . Z definicji dopasowania, | M ( W )| = | W |. A M ( W ) ⊆ N _G ( W ), ponieważ wszystkie elementy M ( W ) są sąsiadami W . Zatem |N _G ( W )| ≥ | M ( W )| i stąd |N _G ( W )| ≥ | W |.

Kierunek twardy : zakładamy, że nie ma X -doskonałego dopasowania i dowodzimy, że warunek Halla jest naruszony dla co najmniej jednego W ⊆ X . Niech M będzie maksymalnym dopasowaniem i niech u będzie wierzchołkiem X nie nasyconym przez M . Rozważ wszystkie naprzemienne ścieżki (tj. ścieżki w G naprzemiennie używające krawędzi na zewnątrz i wewnątrz M ) zaczynając od u . Niech zbiór wszystkich punktów w Y połączonych z u tymi naprzemiennymi ścieżkami będzie Z , a zbiór wszystkich punktów w X połączonych z u tymi naprzemiennymi ścieżkami (włącznie z samym u ) będzie W . Żadna maksymalna ścieżka przemienna nie może kończyć się wierzchołkiem w Y , ponieważ nie byłaby to ścieżka rozszerzająca , abyśmy mogli rozszerzyć M do ściśle większego dopasowania, przełączając status (należy do M lub nie) wszystkich krawędzi ścieżki. Zatem każdy wierzchołek w Z jest dopasowany przez M do wierzchołka w W \ { u }. I odwrotnie, każdy wierzchołek v w W \ { u } jest dopasowywany przez M do wierzchołka w Z (czyli wierzchołka poprzedzającego v na przemiennej ścieżce kończącej się na v ). Zatem M zapewnia bijekcję W \ { u } i Z , co implikuje | W | = | Z | + 1. Z drugiej strony, N _G ( W ) ⊆ Z . Rzeczywiście, niech v w N _G ( W ) będzie połączone z wierzchołkiem w w W . Jeśli krawędź ( w , v ) znajduje się w M , to v poprzedza w na każdej naprzemiennej ścieżce, która biegnie od u do w . Jeśli krawędź ( w , v ) nie znajduje się w M , można jej użyć do przedłużenia dowolnej ścieżki przemiennej biegnącej od u do w . W obu przypadkach v jest odwiedzana przez jakąś naprzemienną ścieżkę wydaną przez u . Stąd N _G ( W ) ⊆ Z , a więc |N _G ( W )| ≤ | Z | = | W | − 1 < | W |.

Konstruktywny dowód twardego kierunku

Zdefiniuj naruszenie Halla jako podzbiór W od X, dla którego |N _G ( W )| < | W |. Jeśli W jest naruszeniem Halla, to nie ma dopasowania, które nasyca wszystkie wierzchołki W . Dlatego też nie ma dopasowania, które nasyca X . Twierdzenie Halla o małżeństwie mówi, że graf zawiera X -idealne dopasowanie wtedy i tylko wtedy, gdy nie zawiera żadnych elementów naruszających Halla. Poniższy algorytm udowadnia twardy kierunek twierdzenia: znajduje albo dopasowanie X- idealne, albo naruszenie Halla. Używa, jako podprogramu, algorytmu, który, mając pasujące M i niedopasowany wierzchołek x ₀ , albo znajduje ścieżkę M- augmentującą, albo błąd Halla zawierający x ₀ .

To używa

1. Zainicjuj M  := {}. // Puste dopasowanie.
2. Twierdzenie: M to dopasowanie w G .
3. Jeśli M nasyconych wszystkie wierzchołki X, a następnie powrócić do X dopasowanie -perfect M .
4. Niech x ₀ będzie niedopasowanym wierzchołkiem (wierzchołek w X \ V( M )).
5. Używając algorytmu naruszającego Halla , znajdź albo naruszającego Halla, albo ścieżkę M- augmenting.
6. W pierwszym przypadku zwróć naruszającego Halla .
7. W drugim przypadku użyj ścieżki M- augmenting, aby zwiększyć rozmiar M (o jedną krawędź) i wróć do kroku 2 .

W każdej iteracji M rośnie o jedną krawędź. Zatem ten algorytm musi zakończyć się po co najwyżej | E | iteracje. Każda iteracja zajmuje najwyżej | X | czas. Całkowita złożoność środowiska wykonawczego jest podobna do metody Forda-Fulkersona służącej do znajdowania dopasowania o maksymalnej kardynalności .

Równoważność formuły kombinatorycznej i formuły grafowo-teoretycznej

Niech S = ( A ₁ , A ₂ , ..., A _n ), gdzie A _i są zbiorami skończonymi, które nie muszą być różne. Niech zbiór X = { A ₁ , A ₂ , ..., A _n } (czyli zbiór nazw elementów S ) oraz zbiór Y będą sumą wszystkich elementów we wszystkich A _i .

Tworzymy skończony graf dwudzielny G  := ( X  + Y , E ), ze zbiorami dwudzielnymi X i Y , łącząc dowolny element w Y z każdym A _i, którego jest członkiem. Poprzecznym z S jest X -perfect dopasowanie (pasujący który obejmuje każdy wierzchołek w X ) dwuczęściowego grafu G . W ten sposób problem w sformułowaniu kombinatorycznym można łatwo przełożyć na problem w sformułowaniu grafowo-teoretycznym.  

Dowód topologiczny

Twierdzenie Halla można udowodnić (niekonstruktywnie) na podstawie lematu Spernera .

Aplikacje

Twierdzenie ma wiele innych interesujących zastosowań „niemałżeńskich”. Na przykład, weź standardową talię kart i rozdaj je na 13 stosów po 4 karty. Następnie, korzystając z twierdzenia o małżeństwie, możemy pokazać, że zawsze można wybrać dokładnie 1 kartę z każdego stosu, tak aby 13 wybranych kart zawierało dokładnie jedną kartę każdej rangi (As, 2, 3, ..., Dama, Król).

Bardziej abstrakcyjny, niech G być grupy , a H jest skończoną podgrupa o G . Następnie twierdzenie o małżeństwie może być użyte do wykazania, że ​​istnieje zbiór T taki, że T jest transwersem zarówno dla zbioru lewych, jak i prawych cosetów H w G .

Twierdzenie o małżeństwie jest używane w zwykłych dowodach na to, że prostokąt łaciński ( r × n ) można zawsze rozszerzyć do prostokąta ( ( r  + 1) × n ) łacińskiego, gdy r < n , a więc ostatecznie do łacińskiego kwadrat .

Równoważności logiczne

Twierdzenie to jest częścią zbioru niezwykle potężnych twierdzeń w kombinatoryce, z których wszystkie są ze sobą powiązane w nieformalnym sensie, ponieważ łatwiej jest udowodnić jedno z tych twierdzeń na podstawie innego z nich niż na podstawie pierwszych zasad. Obejmują one:

• Twierdzenie Königa-Egerváry'ego (1931) ( Dénes Kőnig , Jenő Egerváry )
• twierdzenie Königa
• Twierdzenie Mengera (1927)
• Twierdzenie o maksymalnym przepływie min-cut (algorytm Forda-Fulkersona)
• Twierdzenie Birkhoffa Von Neumanna (1946)
• Twierdzenie Dilwortha .

W szczególności istnieją proste dowody implikacji twierdzenia Dilwortha ⇔ twierdzenia Halla ⇔ twierdzenia Königa-Egerváry'ego ⇔ twierdzenia Königa.

Nieskończone rodziny

Marshall Hall Jr. wariant

Dzięki starannemu zbadaniu oryginalnego dowodu Philipa Halla , Marshall Hall Jr. (bez związku z Philipem Hallem) był w stanie dopracować wynik w sposób, który umożliwił działanie dowodu dla nieskończonego S . Ten wariant doprecyzowuje twierdzenie o małżeństwie i zapewnia dolne ograniczenie liczby przekrojów, które może mieć dane S. Ten wariant to:

Załóżmy, że ( A ₁ , A ₂ , ..., A _n ), gdzie A _i są skończonymi zbiorami, które nie muszą być różne, jest rodziną zbiorów spełniających warunek małżeństwa i załóżmy, że | A _ja | ≥ r dla i = 1, ..., n . Wtedy liczba różnych przekrojów dla rodziny wynosi co najmniej r ! jeśli r ≤ n i r ( r − 1) ... ( r − n + 1) jeśli r > n .

Przypomnijmy, że poprzeczka dla rodziny S jest uporządkowaną sekwencją, więc dwa różne poprzeczne mogą mieć dokładnie te same elementy. Na przykład rodzina A ₁ = {1, 2, 3}, A ₂ = {1, 2, 5} ma zarówno (1, 2), jak i (2, 1) jako odrębne poprzeczki.

Stan małżeństwa nie przedłuża się

Poniższy przykład, autorstwa Marshalla Halla Jr., pokazuje, że warunek małżeństwa nie gwarantuje istnienia transwersalnego w nieskończonej rodzinie, w której dozwolone są nieskończone zbiory.

Niech S będzie rodziną, A ₀ = {1, 2, 3, ...}, A ₁ = {1}, A ₂ = {2}, ..., A _i = { i  }, ...

Warunek małżeństwa obowiązuje dla tej nieskończonej rodziny, ale nie można skonstruować żadnego przekrojowego.

Bardziej ogólny problem wyboru (niekoniecznie odrębnego) elementu z każdego zbioru niepustych zbiorów (bez ograniczeń co do liczby zbiorów lub rozmiaru zbiorów) jest ogólnie dozwolony tylko wtedy, gdy aksjomat wyboru jest przyjęty.

Twierdzenie o małżeństwie rozciąga się na przypadek nieskończony, jeśli zostało poprawnie sformułowane. Mając graf dwudzielny o bokach A i B , mówimy, że podzbiór C zbioru B jest mniejszy lub równy rozmiarowi podzbioru D zbioru A na grafie, jeśli istnieje wstrzyknięcie w grafie (mianowicie, używając tylko krawędzi wykres) od C do D , i że jest on ściśle mniejszy na wykresie, jeśli dodatkowo nie ma wstrzyknięcia na wykresie w przeciwnym kierunku. Zauważ, że pominięcie na wykresie daje zwykłe pojęcie porównania kardynalności. Nieskończone stany twierdzenie, że połączenie nie istnieje dawka od A do B na wykresie, wtedy i tylko wtedy, gdy nie jest podzbiorem C z taki sposób, że N ( C ) jest bezwzględnie mniejsze niż C na wykresie.

Ułamkowy wariant dopasowania

Ułamkową dopasowanie na wykresie jest przypisanie wag nieujemne każdej krawędzi, przy czym suma ciężarów sąsiedztwie każdego wierzchołka wynosi najwyżej 1. ułamkową pasującej X -perfect, że suma wag sąsiedztwie każdego wierzchołka jest dokładnie 1. Poniższe są równoważne dla grafu dwudzielnego G = ( X+Y, E ):

• G przyznaje X-idealne dopasowanie.
• G dopuszcza dopasowanie ułamkowe X-perfect. Implikacja wynika bezpośrednio z faktu, że dopasowanie X -perfect jest szczególnym przypadkiem dopasowania ułamkowego X -perfect, w którym każda waga wynosi 1 (jeśli krawędź jest w dopasowaniu) lub 0 (jeśli nie jest).
• G spełnia warunek małżeństwa Halla. Implikacja jest słuszna, ponieważ dla każdego podzbioru W z X suma wag w pobliżu wierzchołków W wynosi | W |, więc sąsiadujące z nimi krawędzie muszą koniecznie sąsiadować co najmniej z |W| wierzchołki Y .

Wariant ilościowy

Gdy warunek Halla nie jest spełniony, oryginalne twierdzenie mówi nam tylko, że idealne dopasowanie nie istnieje, ale nie mówi, jakie jest największe dopasowanie, jakie istnieje. Aby poznać te informacje, potrzebujemy pojęcia niedoboru grafu . Przy danym dwudzielnym grafie G = ( X + Y , E ), niedobór G wrt X jest maksimum, we wszystkich podzbiorach W od X , różnicy | W | - | N _G ( W )|. Im większy niedobór, tym dalej wykres od spełnienia warunku Halla.

Korzystając z twierdzenia Halla o małżeństwie, można udowodnić, że jeśli niedobór grafu dwudzielnego G wynosi d , to G dopuszcza dopasowanie wielkości co najmniej | X | -d .

Uogólnienia

• Uogólnienie twierdzenia Halla na grafy ogólne (które niekoniecznie są dwudzielne) dostarcza twierdzenie Tutte .
• Uogólnienie twierdzenia Halla na hipergrafy dwudzielne dostarczają różne twierdzenia typu Halla dla hipergrafów .

Uwagi

Bibliografia

• Brualdi, Richard A. (2010), wprowadzające kombinatoryka , Upper Saddle River, NJ: Prentice-Hall / Pearson, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Kombinatoryka: tematy, techniki, algorytmy , Cambridge: Cambridge University Press, ISBN 978-0-521-45761-3
• Dongchen, Jiang; Nipkow, Tobiasz (2010), „Twierdzenie o małżeństwie Halla” , Archiwum dowodów formalnych , ISSN  2150-914X . Dowód sprawdzany komputerowo.CS1 maint: postscript ( link )
• Hall, Jr., Marshall (1986), Teoria kombinatoryczna (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-09138-7
• Hall, Philip (1935), „O przedstawicielach podzbiorów”, J. London Math. Soc. , 10 (1): 26–30, doi : 10.1112/jlms/s1-10.37.26
• Halmos, Paul R .; Vaughan, Herbert E. (1950), "Problem małżeństwa", American Journal of Mathematics , 72 (1): 214-215, doi : 10.2307/2372148 , JSTOR  2372148 , MR  0033330
• Reichmeider, PF (1984), The Equivalence of Some Combinatorial Matching Theorems , Polygonal Publishing House, ISBN 978-0-936428-09-3
• Roberts, Fred S.; Tesman, Barry (2009), kombinatoryka stosowana (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
• van Linta, JH; Wilson, RM (1992), Kurs kombinatoryki , Cambridge: Cambridge University Press, ISBN 978-0-521-42260-4

Zewnętrzne linki

• Twierdzenie o małżeństwie na węźle
• Twierdzenie o małżeństwie i algorytm na przecięciu węzła
• Twierdzenie Halla o małżeństwie wyjaśnione intuicyjnie w notatkach Lucky'ego.

Ten artykuł zawiera materiał z dowodu twierdzenia Halla o małżeństwie w PlanetMath , który jest licencjonowany na licencji Creative Commons Attribution/Share-Alike License .