Podział grafu

[PiotrWP]

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 ?

[Majeskas]

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?"