Ścieżka Hamiltona
Z Wikipedii
Ścieżka Hamiltona – ścieżka w grafie przebiegająca przez wszystkie jego wierzchołki. Graf zawierający ścieżkę Hamiltona jest grafem 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.
Zobacz też: Cykl Hamiltona