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). [dostęp 2026-01-17].
Kategoria:Teoria grafów Kategoria:William Rowan Hamilton