Obwody Hamiltona. Generowanie obwodów Hamiltona.

W roku 1859 irlandzki astronom i matematyk W. Hamilton (1805-1865) wynalazł łamigłówkę i sprzedał ją producentowi gier w Dublinie. Zagadka składała się z drewnianego, regularnego dwunastościanu o dwudziestu rogach, o każdej ścianie w kształcie regularnego pięciokąta o trzech krawędziach zbiegających się w każdym rogu. Rogi oznaczone były nazwami dwudziestu znanych miast, takich jak: Londyn, Nowy Jork, Delhi, Paryż itd. Zadaniem łamigłówki było znalezienie drogi wzdłuż krawędzi dwunastoscianu przechodzącej przez każde z 20 miast dokładnie jeden raz. Nie każdy digraf ma obwód Hamiltona (patrz rysunek niżej).

Liczba różnych obwodów Hamiltona w digrafie pełnym o n wierzchołkach wynosi (n-1)! (w grafie ta liczba jest o dwa razy mniejsza).

Dla generowania obwodów Hamiltona wystarczy szukać jedno cyklowe permutacji lub didrzewa z kodem nie powtarzających się indeksów.

Rys. 5-5.

---