Ś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]
