Cykl Hamiltona a droga Eulera

Rozszerzenie tematu teorii grafów. Droga Eulera odwiedza każdą krawędź raz (jak mosty królewieckie), a cykl Hamiltona każdy wierzchołek raz — pozornie podobne, ale drugi problem jest znacznie trudniejszy obliczeniowo (NP-trudny, związany z problemem komiwojażera). Pojęcie wprowadził William Rowan Hamilton „grą ikozjańską" w 1857 r.

Matematyka · Teoria grafów · Cykl Hamiltona a droga Eulera (1857)

GrafKoperta (5)

Cykl Hamiltona wymaga odwiedzenia dokładnie raz każdego…

wierzchołki

krawędzie

cykl Hamiltona

istnieje

droga Eulera

🎯 Wyzwanie: rozpoznaj trasę Eulera

seria: 0

Dam Ci ciąg stopni wierzchołków — orzeknij typ trasy Eulera. Reguła: 0 nieparzystych → cykl, 2 → droga, inaczej → brak.

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).

\underbrace{\text{Euler} = \text{każda } \textbf{krawędź} \text{ raz}}_{\text{drogi}} \;\;\neq\;\; \underbrace{\text{Hamilton} = \text{każdy } \textbf{wierzchołek} \text{ raz}}_{\text{miasta}}

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.

Model poglądowy · Wirtualne laboratorium NexTutor

Spodobał Ci się eksperyment? Udostępnij go.

Jest darmowy — podeślij znajomym ze szkoły.

Teoria i wzory

Dwa różne warunki droga/cykl Eulera — przez każdą krawędź dokładnie raz, cykl Hamiltona — przez każdy wierzchołek dokładnie raz (z powrotem do startu). Różnica trudności Dla Eulera jest prosty warunek (parzystość stopni wierzchołków). Dla Hamiltona nie znamy szybkiego kryterium — to problem NP-trudny, blisko spokrewniony z problemem komiwojażera. Pochodzenie Pojęcie wprowadził Hamilton „grą ikozjańską” (1857) — szukaniem cyklu po wierzchołkach dwunastościanu.

Uczysz? Umieść ten eksperyment na swojej stronie.

Darmowy widget — wklej na stronę szkoły, bloga lub notatki. Linkuje do pełnej wersji.

Uczysz w klasie albo korepetujesz? Prowadź uczniów w NexTutor →

Najczęstsze pytania

›

Czego wymaga cykl Hamiltona?

Odwiedzenia dokładnie raz każdego wierzchołka grafu i powrotu do startu.

›

Czym różni się cykl Hamiltona od drogi Eulera?

Droga Eulera odwiedza każdą krawędź raz, a cykl Hamiltona każdy wierzchołek raz — to dwa różne warunki.

›

Dlaczego cykl Hamiltona jest trudniejszy?

Nie znamy szybkiego (wielomianowego) algorytmu — to problem NP-trudny, związany z problemem komiwojażera.

Powiązane eksperymenty

Mosty królewieckie — narodziny teorii grafów →Problem komiwojażera — P kontra NP →Twierdzenie o czterech barwach →Algorytmy sortowania — złożoność →