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\wedge u\in V_2)\vee (v\in V_2\wedge 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

$\Vert W\Vert ⩾\Vert K\Vert ,$

gdzie:

$W=\{w\in V_2:(\mathrm{\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$

$\Vert X\Vert$ to moc zbioru $X.$

Jeżeli $\Vert V_1\Vert =\Vert V_2\Vert ,$ 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 𝔸}A\right|⩾|𝔸|$

dla każdego $𝔸\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\ne 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.

Linki zewnętrzne

• Szablon:Pismo Delta