Podać możliwie dokładne warunki, kiedy jest to możliwe, by posadzić grupę m rycerzy, n dam i p dworzan, tak by rycerz nie siedział obok innego rycerza, dama obok damy i dworzanin obok dworzanina.
Da się to sprowadzić do teorii grafu, ale jakoś nie mogłem znaleźć jak (podejrzewam że z wykorzystaniem kolorowania). Czy mógłby ktoś podpowiedzieć, lub rozwiązać to zadanie? Z góry dziękuje
Posadzenie 3 grup przy okrągłym stole
-
- Użytkownik
- Posty: 5
- Rejestracja: 19 cze 2019, o 15:43
- Płeć: Kobieta
- Lokalizacja: Studentka
- Podziękował: 2 razy
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Posadzenie 3 grup przy okrągłym stole
Dworzanin siedzący przy jednym stole z rycerzem?
Jeśli usadzisz najliczniejszą grupę to między jej osobnikami powinna znaleźć się przynajmniej jedna z osób z mniej licznych grup.
I sądzę, że jest to jedyny warunek rozwiązywalności zadania (suma liczności mniej licznych grup jest niemniejsza od ilości osób w najliczniejszej grupie.)-- 23 cze 2019, o 17:55 --A jednak, mogą być jeszcze inne założenia:
- musi być odpowiednio duża liczba krzeseł lub innych siedzisk (ława przy okrągłym stole jest mało funkcjonalna)
- musi istnieć odpowiednio duży okrągły stół
- oraz odpowiednio duże pomieszczenie w którym można ów mebel rozłożyć.
Jeśli usadzisz najliczniejszą grupę to między jej osobnikami powinna znaleźć się przynajmniej jedna z osób z mniej licznych grup.
I sądzę, że jest to jedyny warunek rozwiązywalności zadania (suma liczności mniej licznych grup jest niemniejsza od ilości osób w najliczniejszej grupie.)-- 23 cze 2019, o 17:55 --A jednak, mogą być jeszcze inne założenia:
- musi być odpowiednio duża liczba krzeseł lub innych siedzisk (ława przy okrągłym stole jest mało funkcjonalna)
- musi istnieć odpowiednio duży okrągły stół
- oraz odpowiednio duże pomieszczenie w którym można ów mebel rozłożyć.