Tekst źródłowy strony Twierdzenie o kojarzeniu małżeństw

'''Twierdzenie o kojarzeniu małżeństw''' (twierdzenie Halla) – przypisywane zazwyczaj [[Philip Hall|Philipowi Hallowi]] twierdzenie dotyczące istnienia [[Skojarzenie (teoria grafów)|pełnego skojarzenia]] [[graf dwudzielny|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 [[warunek konieczny|koniecznym]] i [[warunek wystarczający|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 <math>G=(V, E)</math> będzie grafem, i niech <math>V_1 \subseteq V, V_2 \subseteq V</math> będą rozłącznymi podzbiorami zbioru wierzchołków, <math>V_1 \cup V_2 = V,</math> takimi, że jeśli <math>e</math> jest dowolną krawędzią grafu i <math>e = \{v,u\},</math> to spełniony jest warunek
: <math>(v \in V_1 \land u \in V_2) \lor (v \in V_2 \land u \in V_1),</math>

czyli graf <math>G</math> jest grafem dwudzielnym. Wówczas w tym grafie istnieje skojarzenie, którego krawędzie są incydentne ze wszystkimi wierzchołkami z <math>V_1</math> wtedy i tylko wtedy, gdy dla każdego podzbioru wierzchołków <math>K\subseteq V_1</math> zachodzi
: <math>\|W\| \geqslant \|K\|,</math>

gdzie:
: <math>W=\{w \in V_2\colon (\exists k\in K) \{k,w\} \in E\}</math>

to zbiór wierzchołków z <math>V_2</math> połączonych krawędzią z którymkolwiek wierzchołkiem z <math>K</math>
: <math>\|X\|</math> to [[moc zbioru]] <math>X.</math>

Jeżeli <math>\|V_1\|=\|V_2\|,</math> to takie skojarzenie jest pełne (doskonałe).

=== Wersja dla transwersal ===
Twierdzenie Halla dla [[transwersala|transwersal]] mówi, że dla rodziny <math>R</math> istnieje transwersala wtedy i tylko wtedy, gdy dla każdej <math>k</math>-elementowej podrodziny rodziny <math>R</math> mnogościowa suma wszystkich składowych tej podrodziny ma k lub więcej elementów.
: <math>\left|\bigcup_{A\in\mathbb{A}}A \right|\geqslant|\mathbb{A}|</math>

dla każdego <math>\mathbb{A}\subseteq R.</math>

== 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 <math>k</math>-elementowego podzbioru złożonego z elementów tej sumy.

Wystarczalność warunku można udowodnić, korzystając z [[indukcja matematyczna|indukcji matematycznej]]. Przez n oznaczę ilość podzbiorów zbioru <math>A = \{1,2,\dots\}.</math> Zauważmy, że dla <math>n=1</math> twierdzenie jest prawdziwe, bowiem można wybrać jeden dowolny element z <math>S_1.</math> Niech <math>n>1.</math> Zakładamy, że twierdzenie jest prawdziwe dla <math>m=1, \dots, n-1.</math>

Jeżeli dla danego n mnogościowa suma zbiorów <math>S_1, S_2, \dots, S_n</math> ma więcej niż n elementów, to twierdzenie jest prawdziwe, wystarczy bowiem wybrać dowolny element k zbioru <math>\{1,2,\dots,n\},</math> utworzyć transwersalę dla <math>n-1</math>-elementowej rodziny zbiorów <math>\{A_i: i=1,2,\dots,n;\; i \neq m\}</math> (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 <math>\{1,2,\dots,n\}</math> taki, że suma mnogościowa wszystkich elementów zbiorów <math>A_j, j \in J</math> jest równa ilości elementów zbioru J. Wybierzmy teraz transwersalę dla rodziny <math>\{A_j: j \in J\}</math> oraz rodziny <math>\{A_k - B: k \in K\},</math> gdzie <math>K= \{1,\dots,n\} - J,</math> zaś <math>B= \bigcup A_j, j \in J.</math> 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<ref>Halmos Paul R., Vaughan Herbert E., ''The marriage problem'', „American Journal of Mathematics” 72, (1950), s. 214–215.</ref>.

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{Pismo Delta | url = 2024/10/twierdzenie-tuttea-i-twierdzenie-halla/ | autor = Bartłomiej Bzdęga | tytuł = Twierdzenie Tutte’a i twierdzenie Halla | data = październik 2024 | data dostępu = 2024-10-08 }}

{{Teoria grafów}}

{{Kontrola autorytatywna}}

{{SORTUJ:o kojarzeniu małżeństw}}
[[Kategoria:Twierdzenia kombinatoryki]]
[[Kategoria:Twierdzenia teorii grafów]]