alt=Graf o pięciu wierzchołkach z zaznaczoną ścieżką Hamiltona.|mały|Graf półhamiltonowski z wyróżnioną na niebiesko ścieżką Hamiltona. alt=Graf o sześciu wierzchołkach z zaznaczonym cyklem Hamiltona.|mały|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 , 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.
Przykłady Z reguły przyjmuje się, że – graf o jednym wierzchołku jest hamiltonowski. Liczba grafów hamiltonowskich o wierzchołkach jest równa odpowiednio: 1, 0, 1, 3, 8, 48, 383, … . Niektóre klasy grafów mają tę własność, że wszystkie należące do nich grafy są hamiltonowskie:
graf pełny o co najmniej trzech wierzchołkach, pełny graf dwudzielny o co najmniej czterech wierzchołkach, -kostka dla koło dla 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.
Zobacz też cykl Eulera problem komiwojażera
Przypisy
Linki zewnętrzne
Kategoria:Teoria grafów Kategoria:William Rowan Hamilton