Cykle Hamiltona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Clayon
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 1 wrz 2020, o 13:03
Płeć: Mężczyzna
wiek: 19

Cykle Hamiltona

Post autor: Clayon »

Cześć!
Mam problem z takim zadaniem:

Ile cykli Hamiltona posiada graf pełny o \(\displaystyle{ N}\) wierzchołkach?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Cykle Hamiltona

Post autor: kerajs »

Ma on \(\displaystyle{ \frac{(N-1)!}{2}}\) cykli.

Niech wierzchołek A będzie startem każdego z cykli. Pozostałe wierzchołki można ułożyć w ciąg ( wyznaczający kolejne wierzchołki w cyklu) na \(\displaystyle{ (N-1)!}\) sposobów. Skoro po pętelce można można poruszać się w obie strony, to powyższą ilość należy podzielić przez 2.
ODPOWIEDZ