Ścieżka Hamiltona

Ścieżka Hamiltonaścieżka w grafie przebiegająca przez wszystkie jego wierzchołki dokładnie raz. Graf zawierający ścieżkę Hamiltona jest grafem półhamiltonowskim. Odpowiedź na pytanie, czy graf zawiera ścieżkę Hamiltona jest w teorii obliczeń problemem NP-zupełnym, tj. nie istnieją efektywne algorytmy odpowiadające na to pytanie. Wszystkie ścieżki Hamiltona można znaleźć np. przy pomocy metody kompozycji łacińskiej. Niekiedy o grafie, który posiada ścieżkę hamiltonowską oraz nie ma cyklu hamiltonowskiego, mówi się, że jest grafem trasowalnym lub grafem półhamiltonowskim.[potrzebny przypis]

Graf posiadający ścieżkę Hamiltona. Niebieska kropka to wierzchołek grafu, strzałka to krawędź grafu. Na czerwono oznaczono ścieżkę Hamiltona

Zobacz teżEdytuj