szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 lut 2017, o 13:06 
Użytkownik

Posty: 25
Lokalizacja: Poznań
Mamy 2n uczniów, z których każdy ma przynajmniej n przyjaciół. Pokaż, że można ich usadzić w n ławkach tak, by każdy z nich siedział z przyjacielem. Pokaż też, że jeśli n \ge  1, to może być to zrobione na conajmniej dwa sposoby.
Góra
Mężczyzna Offline
PostNapisane: 17 lut 2017, o 17:27 
Użytkownik

Posty: 1038
Lokalizacja: Lublin/Warszawa
Zróbmy graf, w którym uczniowie to wierzchołki, a każda para uczniów, którzy się znają jest połączona krawędzią.
Na mocy twierdzenia Diraca w tym grafie jest cykl Hamiltona.
Wybieramy z tego cyklu co drugą krawędź. Możemy to zrobić na dwa sposoby.
Każdy z tych dwóch sposobów wyborów odpowiada pewnemu usadzeniu w ławkach - usadzamy uczniów połączonych krawędzią w jednej ławce.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Na ile sposobow możemy powiesić na ścianie 8 obrazów  s147698  5
 Na ile sposobow mozna ustawic kolejke:  Arleta19912  1
 Na ile sposobów na ławce może usiąść 11 graczy jeśli  Roudin  6
 Iloma sposobami mozna przydzielic robotnikom zajecie?  lobuziak  4
 ile jest sposobów rozmieszczenia n kul w n-3 pudełkach  adamigo10000  12
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl