W roku 1856 sir William Rowan Hamilton postanowił trochę zarobić, więc zaczął sprzedawać następującą łamigłowkę. Wyobraźmy sobie drewniany klocek o kształcie dwunastościanu foremnego. Należało znaleźć drogę złożoną z krawędzi klocka przechodzącą dokładnie raz przez każdy jego wierzchołek i wracającą do wierzchołka wyjściowego.

Taką drogę w grafie nazywamy cyklem Hamiltona.

??? Rozwiązanie zagadki sir Hamiltona sprowadza się do znalezienia cyklu Hamiltona w poniższym grafie. Sprawdź, czy potrafisz.

---

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej