Cykl Hamiltona.html



Graf hamiltonowski. Niebieskie kropki oznaczają wierzchołki grafu, strzałki to krawędzie grafu, a na czerwono oznaczono cykl hamiltonowski

Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu występuje jeden raz. 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.

Zobacz też: graf hamiltonowski, cykl Eulera, algorytm najbliższego sąsiada