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 ${\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=\{v,u\},}$ 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)\{k,w\}\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=\{1,2,\dots \}.}$ 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 \{1,2,\dots ,n\},}$ utworzyć transwersalę dla ${\displaystyle n-1}$-elementowej rodziny zbiorów ${\displaystyle \{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 ${\displaystyle \{1,2,\dots ,n\}}$ 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 \{A_{j}:j\in J\}}$ oraz rodziny ${\displaystyle \{A_{k}-B:k\in K\},}$ gdzie ${\displaystyle K=\{1,\dots ,n\}-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