Twierdzenie o kojarzeniu małżeństw

Z Wikipedii

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

Najważniejsze pojęcia
graf
podgraf
cykl
klika
stopień wierzchołka
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
Breadth-first search
Depth-first search
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
najbliższego sąsiada

Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem kojarzenia małżeństw

Inne zagadnienia
kod Graya
diagram Hassego

edytuj ten szablon

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 nosi 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 \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 \and u \in V_2) \or (v \in V_2 \and 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 \subset V_1, K=\lbrace k_1, k_2, \ldots, k_n\rbrace$ zachodzi nierówność

$\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

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|\geq|\mathbb{A}|$

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

[edytuj] 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 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.