szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Podział grafu
PostNapisane: 14 cze 2016, o 16:27 
Użytkownik

Posty: 293
Lokalizacja: Warszawa
Na ile sposobów można podzielić graf składający się z 2n elementów.

W odpowiedzi mam \frac{{2n \choose n} }{2} jednak nie wiem skąd taki wynik.Czy przypadkiem nie chodzi o bisekcję ? Czy chodzi o graf pełny ?
Góra
Mężczyzna Offline
 Tytuł: Podział grafu
PostNapisane: 15 cze 2016, o 10:35 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Należałoby zacząć od pytania: "co to znaczy podzielić graf?". Odpowiedź sugeruje niezbyt grafowe rozumowanie. Weźmy zbiór 2n osób i zastanówmy się, na ile sposób możemy podzielić go na dwie drużyny. Najpierw wybieramy 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 2n wierzchołków. Na ile sposobów możemy podzielić zbiór wierzchołków tego grafu na dwa równoliczne bloki?"
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 rozklad grafu na trojkaty  nologin  1
 podział na klasy w kartografii  bregalad  5
 Podział turystów na kolejki  vtvs  2
 Podział miejsc w rzedzie  awd19  4
 Liczba krawędzi w dopełnieniu grafu regularnego  stefan13  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl