Cześć!
Mam problem z takim zadaniem:
Ile cykli Hamiltona posiada graf pełny o \(\displaystyle{ N}\) wierzchołkach?
Cykle Hamiltona
- kerajs
- 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
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.
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.