Otwórz menu główne

Twierdzenie o kojarzeniu małżeństw

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




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


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


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Twierdzenie o kojarzeniu małżeństw (twierdzenie Halla) – przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane 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? 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.

TwierdzenieEdytuj

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

Wersja dla grafówEdytuj

Niech   będzie grafem, i niech   będą rozłącznymi podzbiorami zbioru wierzchołków,   takimi, że jeśli   jest dowolną krawędzią grafu i   to spełniony jest warunek

 

czyli graf   jest grafem dwudzielnym. Wówczas w tym grafie istnieje skojarzenie, którego krawędzie są incydentne ze wszystkimi wierzchołkami z   wtedy i tylko wtedy, gdy dla każdego podzbioru wierzchołków   zachodzi

 

gdzie:

 

to zbiór wierzchołków z   połączonych krawędzią z którymkolwiek wierzchołkiem z  

  to moc zbioru  

Jeżeli   to takie skojarzenie jest pełne (doskonałe).

Wersja dla transwersalEdytuj

Twierdzenie Halla dla transwersal mówi, że dla rodziny   istnieje transwersala wtedy i tylko wtedy, gdy dla każdej  -elementowej podrodziny rodziny   mnogościowa suma wszystkich składowych tej podrodziny ma k lub więcej elementów.

 

dla każdego  

DowódEdytuj

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  -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   Zauważmy, że dla   twierdzenie jest prawdziwe, bowiem można wybrać jeden dowolny element z   Niech   Zakładamy, że twierdzenie jest prawdziwe dla  

Jeżeli dla danego n mnogościowa suma zbiorów   ma więcej niż n elementów, to twierdzenie jest prawdziwe, wystarczy bowiem wybrać dowolny element k zbioru   utworzyć transwersalę dla  -elementowej rodziny zbiorów   (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   taki, że suma mnogościowa wszystkich elementów zbiorów   jest równa ilości elementów zbioru J. Wybierzmy teraz transwersalę dla rodziny   oraz rodziny   gdzie   zaś   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].

PrzypisyEdytuj

  1. Halmos Paul R., Vaughan Herbert E., The marriage problem, „American Journal of Mathematics” 72, (1950), s. 214–215.