Cykl Hamiltona

Z Wikipedii, wolnej encyklopedii

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 nazywamy hamiltonowskimi[1].

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 213. ISBN 0-387-95014-1.