graf Hamiltona

graf Hamiltona,

mat. graf, w którym istnieje droga zamknięta zawierająca każdy wierzchołek dokładnie raz (cykl Hamiltona);

W.R. Hamilton zaproponował grę polegającą na znalezieniu drogi wzdłuż krawędzi dwunastościanu foremnego, która przechodzi przez każdy jego wierzchołek dokładnie raz; nie są znane żadne warunki konieczne i dostateczne na to, aby graf zawierał cykl Hamiltona; problem istnienia cyklu Hamiltona w grafie jest NP-zupełny (NP-zupełne problemy); problem znalezienia najkrótszego cyklu przechodzącego przez każdy wierzchołek grafu przynajmniej raz ma wiele zastosowań (np. komiwojażera zadanie), nie ma natomiast efektywnego algorytmu rozwiązywania.