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[1].
Zobacz też
- Twierdzenie Orego
- graf hamiltonowski
- cykl Eulera
- algorytm najbliższego sąsiada
Przypisy
- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 213. ISBN 0-387-95014-1.
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |
- Britannica: science/Hamilton-circuit