graf Hamiltona
 
Encyklopedia PWN
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.
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia