Twierdzenie o kojarzeniu małżeństw

Twierdzenie o kojarzeniu małżeństw (twierdzenie Halla) – przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane w 1935 roku. 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 $G=(V,E)$ będzie grafem, i niech $V_{1}\subseteq V,V_{2}\subseteq V$ będą rozłącznymi podzbiorami zbioru wierzchołków, $V_{1}\cup V_{2}=V,$ takimi, że jeśli $e$ jest dowolną krawędzią grafu i $e=\{v,u\},$ to spełniony jest warunek

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

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

$\|W\|\geqslant \|K\|,$

gdzie:

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

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

$\|X\|$ to moc zbioru $X.$

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

Wersja dla transwersal

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

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

dla każdego $\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 $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 $A=\{1,2,\dots \}.$ Zauważmy, że dla $n=1$ twierdzenie jest prawdziwe, bowiem można wybrać jeden dowolny element z $S_{1}.$ Niech $n>1.$ Zakładamy, że twierdzenie jest prawdziwe dla $m=1,\dots ,n-1.$

Jeżeli dla danego n mnogościowa suma zbiorów $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 $\{1,2,\dots ,n\},$ utworzyć transwersalę dla $n-1$-elementowej rodziny zbiorów $\{A_{i}:i=1,2,\dots ,n;\;i\neq m\}$ (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 $\{1,2,\dots ,n\}$ taki, że suma mnogościowa wszystkich elementów zbiorów $A_{j},j\in J$ jest równa ilości elementów zbioru J. Wybierzmy teraz transwersalę dla rodziny $\{A_{j}:j\in J\}$ oraz rodziny $\{A_{k}-B:k\in K\},$ gdzie $K=\{1,\dots ,n\}-J,$ zaś $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.