Problem kojarzenia małżeństw

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kleszczuk
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 25 cze 2014, o 14:49
Płeć: Mężczyzna
Lokalizacja: Warszawa

Problem kojarzenia małżeństw

Post autor: kleszczuk »

Niech \(\displaystyle{ \left[ 5\right]}\) będzie zbiorem dziewczyn. Niech \(\displaystyle{ {c_{1}, c_{2}, c_{3}, c_{4}, c_{5} }}\) będzie zbiorem chłopaków. Niech \(\displaystyle{ A _{i}}\) oznacza zbiór chłopaków którzy podobają się dziewczynie i, gdzie \(\displaystyle{ A_{i} = {c_{1} }, A_{2} = {c_{2} ,c_{3} }, A_{3} = { c_{1}, c_{2} }, A_{4} = {c_{1}, c_{3} }, A_{5} = { c_{1}, c_{4}, c_{5} }}\) Zbadać czy da się wszystkie dziewczyny wydać za mąż za chłopaków, którzy im się podobają tak, aby żaden chłopak nie był mężem więcej niż jednej dziewczyny.


Po narysowaniu grafu dwudzielnego to wszystko widać, ale jak to formalnie udowodnić?
Jytug
Użytkownik
Użytkownik
Posty: 73
Rejestracja: 10 gru 2012, o 12:21
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 11 razy

Problem kojarzenia małżeństw

Post autor: Jytug »

Twierdzenie Halla mówi o tym w ścisły sposób, wystarczy sprawdzić jego założenia
ODPOWIEDZ