Na stronie używamy cookies. Korzystanie z witryny oznacza zgodę na ich wykorzystywanie. Szczegóły znajdziesz w Regulaminie.
ZAMKNIJ X

Problem kojarzenia małżeństw (twierdzenie Halla)

Ostatnio komentowane
głupie do rzeczy na drugi raz
felisityfornow • 2016-12-10 17:19:44
Spoko?
DOWNN • 2016-12-10 15:00:50
Jest ok
Uczeń2002 • 2016-12-10 13:39:29
za trudne do zrozumienia
ola, 12 lat • 2016-12-10 11:51:46
takie se
szpilllla • 2016-12-09 15:16:18
Autor:
Drukuj
Drukuj
Rozmiar
AAA

Problem kojarzenia małżeństw (twierdzenie Halla)

Wyobraźmy sobie, że mamy grupę k kobiet i m mężczyzn, wszyscy stanu wolnego, oraz każda kobieta ma listę mężczyzn, których byłaby skłonna poślubić.

Czy jest możliwe takie połączenie osób w pary (przez parę rozumiemy skojarzenie kobieta-mężczyzna) by każda panna dostała swojego kawalera?

Okazuje się, że tak - o ile spełniony jest warunek, że każde k dziewczyn zna co najmniej k kawalerów.

W takiej sytuacji odpowiednie połączenie kobiet i mężczyzn nazywamy skojarzeniem doskonałym, a powyższe twierdzenie podające warunek konieczny i wystarczający zarazem, nazywamy twierdzeniem Halla (o kojarzeniu małżeństw).

 

Przykład:

Połączenia pokazują którego z kawalerów zna dana panna.

W tej grupie istnieje skojarzenie doskonałe.

 

A jak sytuacja wygląda w przypadku poniższej grupy z tak zadaną siatką znajomości? 

Warunek konieczny nie jest spełniony, zatem dla tej grupy nie istnieje skojarzenie doskonałe (ponieważ da się wskazać dwie panny, które znają tylko jednego mężczyznę).

 

Twierdzenie Halla znajduje zastosowanie w wielu sytuacjach ze świata rzeczywistego i być może małżeństwa nie są tutaj najlepszym przykładem. Inne przypadki sytuacji, które dają się modelować w podobny sposób to np. aplikowanie studentów na uczelnie wyższe lub przydzielanie zadań pracownikom w firmie.

Polecamy również:

Komentarze (0)
3 + 2 =