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
Jebać żydów
Kruszwil • 2018-07-16 02:16:06
Chcesz się bezpłatnie nauczyć języka angielskiego? Zgłoś się na kurs języka angiel...
Bezpłatne szkolenia • 2018-07-13 09:15:31
@Hasher To zależy już od tłumacza przekładu(Pisma zostały napisane w kilku językach ...
Hgfhfg • 2018-07-09 11:34:37
ok
andrzej duda • 2018-06-14 10:31:18
Super na spr.
Evogy • 2018-06-07 17:45:08
Autor:
Drukuj
Drukuj
Rozmiar
AAA

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 + 1 =