Graf hamiltonowski

Graf hamiltonowski – rodzaj grafu rozważany w teorii grafów i definiowany dwojako, w dwóch nieco innych znaczeniach:

• szerszym: dowolny graf zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona;
• węższym: grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona^[1].

W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim^[2].

Aby lepiej zrozumieć właściwości grafu hamiltonowskiego można się posłużyć przykładem komiwojażera, który chce odwiedzić wszystkich swoich klientów, ale tylko raz (problem komiwojażera). Klienci to wierzchołki grafu, a drogi między nimi są jego krawędziami. Jeżeli graf jest hamiltonowski, to znaczy, że komiwojażer może obejść wszystkich klientów bez mijania drugi raz żadnego z nich i wrócić do punktu wyjścia.