Ścieżka Hamiltona

Graf półhamiltonowski z wyróżnioną na niebiesko ścieżką Hamiltona.

Graf hamiltonowski z wyróżnionym na czerwono cyklem Hamiltona.

Ścieżka Hamiltona – w teorii grafów, ścieżka, która przechodzi przez każdy wierzchołek grafu dokładnie raz. Ścieżkę zamkniętą o tej własności nazywa się cyklem Hamiltona, a graf ją zawierający – grafem hamiltonowskim. Graf niehamiltonowski, ale posiadający ścieżkę Hamiltona nazywa się czasem półhamiltonowskim.

W przeciwieństwie do grafów eulerowskich, nie jest znana (i prawdopodobnie nie istnieje) prosta charakteryzacja tych grafów, które zawierają cykl Hamiltona. Problem rozstrzygnięcia, czy graf jest hamiltonowski nie ma znanego efektywnego algorytmu rozwiązywania, co więcej jest to problem NP-zupełny.

Wymienione tu pojęcia noszą nazwisko Williama Hamiltona, który zaproponował grę polegającą na znalezieniu cyklu wzdłuż krawędzi dwunastościanu foremnego. Problem cykli Hamiltona w grafach wielościanów był jednak badany już rok wcześniej przez Szablon:Link-interwiki, który podał między innymi przykład wielościanu bez cykli Hamiltona. Ze znajdowaniem ścieżek i cykli Hamiltona związany jest także problem skoczka szachowego badany już w IX wieku. Obchodami skoczka interesowali się również w XVIII-wieczni matematycy: Abraham de Moivre oraz Leonhard Euler.

• 
  Dwunastościan foremny z zaznaczonym przykładowym rozwiązaniem gry Hamiltona.
• 
  Ten sam cykl zaznaczony w grafie płaskim dwunastościanu foremnego.

Przykłady

Z reguły przyjmuje się, że $K_1$ – graf o jednym wierzchołku jest hamiltonowski. Liczba grafów hamiltonowskich o $n=1,2,3\dots$ wierzchołkach jest równa odpowiednio:

1, 0, 1, 3, 8, 48, 383, … Szablon:OEIS.

Niektóre klasy grafów mają tę własność, że wszystkie należące do nich grafy są hamiltonowskie:

• graf pełny $K_n$ o co najmniej trzech wierzchołkach,
• pełny graf dwudzielny $K_{n,n}$ o co najmniej czterech wierzchołkach,
• $n$-kostka $Q_n$ dla $n\ge 2,$
• koło $W_n$ dla $n\ge 4,$
• grafy platońskie (wielościanów foremnych),
• grafy wielościanów półforemnych.

Każdy graf wielościanu o co najwyżej 10 wierzchołkach jest hamiltonowski. Istnieją 74 niehamiltonowskie grafy wielościanów o 11 wierzchołkach. Spośród nich najmniej krawędzi ma graf Herschela. Szablon:Grafika rozwinięta

Zobacz też

• cykl Eulera
• problem komiwojażera