Cykl Hamiltona

Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu odwiedzany jest dokładnie raz (oprócz pierwszego wierzchołka). Analogicznie, ścieżka Hamiltona to taka ścieżka w której każdy wierzchołek odwiedzony jest dokładnie raz. Nazwa cyklu i ścieżki pochodzi od irlandzkiego matematyka Hamiltona.

Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywane są hamiltonowskimi.

Zobacz też

• Twierdzenie Orego
• graf hamiltonowski
• cykl Eulera
• algorytm najbliższego sąsiada

Przypisy

Linki zewnętrzne

• Oskar Skibski, Cykl Eulera i Hamiltona [w:] Matematyka Dyskretna, kanał autorski na YouTube, 27 kwietnia 2020 [dostęp 2026-01-17] – nagranie w ramach kursu, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW).
• Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Cycle, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2026-01-17].