Na ile sposobów można podzielić graf składający się z \(\displaystyle{ 2n}\) elementów.
W odpowiedzi mam \(\displaystyle{ \frac{{2n \choose n} }{2}}\) jednak nie wiem skąd taki wynik.Czy przypadkiem nie chodzi o bisekcję ? Czy chodzi o graf pełny ?
Podział grafu
-
- Użytkownik
- Posty: 293
- Rejestracja: 7 paź 2014, o 21:15
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 124 razy
Podział grafu
Ostatnio zmieniony 14 cze 2016, o 22:15 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Podział grafu
Należałoby zacząć od pytania: "co to znaczy podzielić graf?". Odpowiedź sugeruje niezbyt grafowe rozumowanie. Weźmy zbiór \(\displaystyle{ 2n}\) osób i zastanówmy się, na ile sposób możemy podzielić go na dwie drużyny. Najpierw wybieramy \(\displaystyle{ n}\)-tkę osób i ona utworzy pierwszą drużynę. Pozostali utworzą drugą. No ale przy tak zadanym pytaniu nie ma żadnej pierwszej i drugiej drużyny, one nie są numerowane. Dlatego każdy wybór policzyliśmy dwukrotnie, więc wynik należy poprawić. No i dostajemy wynik z odpowiedzi. Jak widać, żadnych grafów tu nie było. A gdyby koniecznie miały być, to treść można by uzupełnić tak: "Bierzemy pewien graf na zbiorze \(\displaystyle{ 2n}\) wierzchołków. Na ile sposobów możemy podzielić zbiór wierzchołków tego grafu na dwa równoliczne bloki?"