Twierdzenie o kojarzeniu małżeństw

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Twierdzenie o kojarzeniu małżeństw - przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformuowane 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? Oczywiście, tacy kandydaci nie mogą się powtarzać.

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

Okazuje się, ze warunkiem konieczym 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.

Spis treści

1 Twierdzenie
- 1.1 Wersja dla grafów
- 1.2 Wersja dla transwersal
2 Dowód
3 Zobacz też

[edytuj] Twierdzenie

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

[edytuj] Wersja dla grafów

Niech $G = (V, E)$ będzie grafem, i niech $V_1 \in V, V_2 \in V$ będą rozłącznymi podzbiorami zbioru wierzchołków, $V_1 \cap V_2 = \emptyset , V_1 \cup V_2 = V$ , takimi, że jeśli e jest dowolną krawędzią grafu i $e = {v, u}$ , to $(v \in V_1 \and u \in V_2) \or (v \in V_2 \and u \in V_1)$ , czyli graf 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 \subset V_1, K=\lbrace k_1, k_2, ..., k_n\rbrace$ zachodzi własność $\sum_{i=0}^n deg(k_i) \ge |W|$ , gdzie $W$ jest zbiorem wierzchołków należących do $V 2$ i mających wspólną krawędź z wierzchołkiem z $K$

Jeżeli moce zbiorów $K, W$ są równe, to takie skojarzenie jest pełne (doskonałe).

[edytuj] Wersja dla transwersal

Niech $A$ będzie zbiorem i $R = \lbrace S_1, S_2, \dots\rbrace$ będzie pewną (niekoniecznie skończoną) rodziną jego skończonych podzbiorów. Transwersalą (systemem różnych reprezentantów) tej rodziny nazywamy podzbiór zbioru $A$ (o ile istnieje) taki, który zawiera dokładnie po jednym elemencie z każdego ze zbiorów $S_1, S_2, \dots$ , to znaczy $A = \lbrace x_1, x_2, \dots\rbrace; x_1 \in S_1, x_2 \in S_2, \dots$ .

Twierdzenie Halla 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.

[edytuj] Dowód

Podany dowód jest sformuowany dla transwersal, dla drzew jest on analogiczny.

Oczywiste jest, iż jest to warunek konieczny, bowiem gdyby nie był on spełniony i suma mnogościowa pewnej 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= \lbrace 1, 2, \dots \rbrace$ . 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, wystarcz bowiem wybrać dowolny element k zbioru $\lbrace 1, 2, \dots, n \rbrace$ , utworzyć transwersalę dla n-1-elementowej rodziny zbiorów $\lbrace A_i: i=1, 2, \dots, n; i \not = 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 $\lbrace 1, 2, \dots, n \rbrace$ 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 $\lbrace A_j: j \in J \rbrace$ oraz rodziny $\lbrace A_k - B: k \in K \rbrace$ , gdzie $K= \lbrace 1, \dots, n \rbrace - 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.