Twierdzenie o kojarzeniu małżeństw

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Twierdzenie o kojarzeniu małżeństw (twierdzenie Halla) – przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane w roku 1935. Jest ono często ilustrowane poprzez przedstawienie następującego problemu:

Mamy dwie grupy – dziewcząt i chłopców – oraz pewną sieć znajomości, to znaczy wiemy, których chłopców z tej grupy zna każda z dziewczyn. Kiedy zachodzi sytuacja, w której każdej dziewczynie można przyporządkować jednego kandydata na męża? Tacy kandydaci nie mogą się powtarzać.

Rozwiązanie tak postawionego problemu nosi nazwę twierdzenia o kojarzeniu małżeństw.

Okazuje się, że warunkiem koniecznym i warunkiem wystarczającym na to, by istniało takie skojarzenie par, jest to, by każda podgrupa dziewcząt licząca k osób znała co najmniej k chłopców.

Twierdzenie

Twierdzenie można przełożyć na język matematyki na kilka sposobów:

Wersja dla grafów

Niech ${\displaystyle G=(V,E)}$ będzie grafem, i niech ${\displaystyle V_{1}\subseteq V,V_{2}\subseteq V}$ będą rozłącznymi podzbiorami zbioru wierzchołków, ${\displaystyle V_{1}\cup V_{2}=V,}$ takimi, że jeśli ${\displaystyle e}$ jest dowolną krawędzią grafu i ${\displaystyle e=\lbrace v,u\rbrace ,}$ to spełniony jest warunek

${\displaystyle (v\in V_{1}\land u\in V_{2})\lor (v\in V_{2}\land u\in V_{1}),}$

czyli graf ${\displaystyle G}$ jest grafem dwudzielnym. Wówczas w tym grafie istnieje skojarzenie, którego krawędzie są incydentne ze wszystkimi wierzchołkami z ${\displaystyle V_{1}}$ wtedy i tylko wtedy, gdy dla każdego podzbioru wierzchołków ${\displaystyle K\subseteq V_{1}}$ zachodzi

${\displaystyle \|W\|\geqslant \|K\|,}$

gdzie:

${\displaystyle W=\{w\in V_{2}\colon (\exists k\in K)\lbrace k,w\rbrace \in E\}}$

to zbiór wierzchołków z ${\displaystyle V_{2}}$ połączonych krawędzią z którymkolwiek wierzchołkiem z ${\displaystyle K}$

${\displaystyle \|X\|}$ to moc zbioru ${\displaystyle X.}$

Jeżeli ${\displaystyle \|V_{1}\|=\|V_{2}\|,}$ to takie skojarzenie jest pełne (doskonałe).

Wersja dla transwersal

Twierdzenie Halla dla transwersal mówi, że dla rodziny ${\displaystyle R}$ istnieje transwersala wtedy i tylko wtedy, gdy dla każdej ${\displaystyle k}$-elementowej podrodziny rodziny ${\displaystyle R}$ mnogościowa suma wszystkich składowych tej podrodziny ma k lub więcej elementów.

${\displaystyle \left|\bigcup _{A\in \mathbb {A} }A\right|\geqslant |\mathbb {A} |}$

dla każdego ${\displaystyle \mathbb {A} \subseteq R.}$

Dowód

Podany dowód jest sformułowany dla transwersal, dla grafów jest on analogiczny.

Oczywiste jest, iż jest to warunek konieczny, bowiem gdyby nie był on spełniony i suma mnogościowa elementów pewnej rodziny zbiorów miała mniej niż k-elementów, to nie byłoby możliwe wybranie ${\displaystyle k}$-elementowego podzbioru złożonego z elementów tej sumy.

Wystarczalność warunku można udowodnić, korzystając z indukcji matematycznej. Przez n oznaczę ilość podzbiorów zbioru ${\displaystyle A=\lbrace 1,2,\dots \rbrace .}$ Zauważmy, że dla ${\displaystyle n=1}$ twierdzenie jest prawdziwe, bowiem można wybrać jeden dowolny element z ${\displaystyle S_{1}.}$ Niech ${\displaystyle n>1.}$ Zakładamy, że twierdzenie jest prawdziwe dla ${\displaystyle m=1,\dots ,n-1.}$

Jeżeli dla danego n mnogościowa suma zbiorów ${\displaystyle S_{1},S_{2},\dots ,S_{n}}$ ma więcej niż n elementów, to twierdzenie jest prawdziwe, wystarczy bowiem wybrać dowolny element k zbioru ${\displaystyle \lbrace 1,2,\dots ,n\rbrace ,}$ utworzyć transwersalę dla ${\displaystyle n-1}$-elementowej rodziny zbiorów ${\displaystyle \lbrace A_{i}:i=1,2,\dots ,n;\;i\neq m\rbrace }$ (co jest możliwe na mocy założenia indukcyjnego) oraz dołączyć do niej element k.

W przeciwnym wypadku istnieje pewien podzbiór J (właściwy) zbioru ${\displaystyle \lbrace 1,2,\dots ,n\rbrace }$ taki, że suma mnogościowa wszystkich elementów zbiorów ${\displaystyle A_{j},j\in J}$ jest równa ilości elementów zbioru J. Wybierzmy teraz transwersalę dla rodziny ${\displaystyle \lbrace A_{j}:j\in J\rbrace }$ oraz rodziny ${\displaystyle \lbrace A_{k}-B:k\in K\rbrace ,}$ gdzie ${\displaystyle K=\lbrace 1,\dots ,n\rbrace -J,}$ zaś ${\displaystyle B=\bigcup A_{j},j\in J.}$ Dla obu rodzin na mocy założenia indukcyjnego istnieją transwersale, i są one rozłączne, co wynika z powyższych warunków. Poszukiwaną transwersalą jest więc zbiór, będący sumą tych transwersal^[1].

Przypisy