Ścieżka Hamiltona: Różnice pomiędzy wersjami

'''Ścieżka Hamiltona''' – [[ścieżka]] w [[graf (matematyka)|grafie]] przebiegająca przez wszystkie jego [[wierzchołek|wierzchołki]] dokładnie raz. Graf zawierający ścieżkę Hamiltona jest [[Graf Hamiltonowski|grafem hamiltonowskim]]półhamiltonowskim. Odpowiedź na pytanie, czy graf zawiera ścieżkę Hamiltona jest w [[teoria obliczeń|teorii obliczeń]] [[Problem NP-zupełny|problemem NP-zupełnym]], tj. nie istnieją efektywne [[algorytm]]y odpowiadające na to pytanie. Wszystkie ścieżki Hamiltona można znaleźć np. przy pomocy [[Metoda kompozycji łacińskiej|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'''.