Cykl Hamiltona a droga Eulera

Co to jest cykl Hamiltona?

Cykl Hamiltona to trasa w grafie, która odwiedza każdy wierzchołek dokładnie raz i wraca do punktu startu. Nazwa pochodzi od irlandzkiego matematyka Williama Rowana Hamiltona, który w 1857 r. wymyślił „grę ikozjańską" (Icosian game) — łamigłówkę polegającą na znalezieniu takiej trasy po wierzchołkach dwunastościanu, sprzedawaną jako gra „Dookoła świata".

Bliźniaczo podobne, a fundamentalnie różne

Pozornie cykl Hamiltona przypomina drogę Eulera (z problemu mostów królewieckich), ale różnica jest zasadnicza: droga Eulera dotyczy krawędzi (przejść po wszystkich drogach), a cykl Hamiltona — wierzchołków (odwiedzenia wszystkich miast).

Ta różnica ma ogromne konsekwencje obliczeniowe

Dla drogi Eulera istnieje prosty warunek (liczba wierzchołków nieparzystego stopnia równa $0$ lub $2$) i szybki algorytm. Dla cyklu Hamiltona nie znamy żadnego szybkiego (wielomianowego) algorytmu — to problem NP-trudny, obliczeniowo bardzo trudny, ściśle związany z problemem komiwojażera i słynnym pytaniem $P \overset{?}{=} NP$.

Oba warunki są niezależne

Graf może mieć jedno, drugie, oba albo żadne. Sześcian (8 wierzchołków) ma cykl Hamiltona, ale nie ma drogi Eulera — wszystkie wierzchołki mają nieparzysty stopień 3. Pięciokąt ma i cykl Hamiltona, i cykl Eulera. Koperta (słynna łamigłówka „narysuj bez odrywania ręki") ma drogę Eulera, a przy okazji także cykl Hamiltona.

Po co Ci to na maturze:

Formalnie teoria grafów nie jest osobnym działem matury, ale ten przykład uczy cennego nawyku: drobna zmiana w sformułowaniu problemu (krawędzie → wierzchołki) może zamienić zadanie łatwe w bardzo trudne. Rozróżnianie „co dokładnie liczymy" — krawędzie czy wierzchołki, elementy czy pary — to podstawa poprawnego rozumowania w kombinatoryce.

Zapamiętaj: droga Eulera = każda krawędź raz (łatwa, prosty warunek); cykl Hamiltona = każdy wierzchołek raz i powrót (NP-trudny). To dwa różne warunki — nie myl ich.