Graf hamiltonowski

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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.

Przykłady grafów hamiltonowskich

Graf skierowany posiadający ścieżkę Hamiltona. Niebieskie kropki to wierzchołki grafu, strzałki to krawędzie grafu, a ścieżkę hamiltona oznaczono kolorem czerwonym.

Przykładowy cykl Hamiltona w grafie dwunastościanu foremnego

Grafem hamiltonowskim w szczególności jest każdy graf:

• pełny, posiadający przynajmniej 3 wierzchołki,
• opisujący wielościan foremny.

Złożoność czasowa

Nie są znane algorytmy umożliwiające jednoznaczne rozwiązanie problemu znajdowania najkrótszej możliwej ścieżki Hamiltona w czasie wielomianowym i działające dla wszystkich możliwych grafów (problem ścieżki Hamiltona jest NP zupełny). W praktyce najczęściej stosowane są algorytmy genetyczne, często wykorzystywane w połączeniu z heurystycznymi (np. heurystyka najbliższego sąsiada). Są to jednak metody dające w większości jedynie rozwiązania bliskie optymalnemu. Znalezienie najlepszego, możliwego rozwiązania, zależy głównie od liczby punktów oraz czasem szczęścia na skutek generacji populacji początkowej, krzyżowania oraz mutacji w algorytmach genetycznych.

Problem złożoności czasowej znajdowania rozwiązania problemu grafu hamiltonowskiego wiąże się z brakiem twierdzenia takiego jak twierdzenie Eulera dla grafów Eulera. Owo twierdzenie pozwala w czasie liniowym (tj. zależnym liniowo od, w tym przypadku, liczby wierzchołków) znaleźć odpowiedź na pytanie, czy graf jest eulerowski. W przypadku grafów Hamiltona twierdzenie takie prawdopodobnie nie istnieje.

Znalezienie algorytmu znajdowania drogi Hamiltona w czasie wielomianowym jest „Świętym Graalem” informatyki, i chociaż powstały już setki publikacji opisujących rzekomo taki właśnie algorytm, problem jest nadal otwarty. Według znakomitej części specjalistów taki algorytm nie istnieje („gdyż, zgodnie z rachunkiem prawdopodobieństwa, ktoś już by taki algorytm znalazł”), jednak do czasu udowodnienia, że takowy algorytm nie istnieje, lub udowodnienia, że taki dowód nie może zostać przeprowadzony, należy wstrzymać się z kategorycznymi osądami.

Przykładowy cykl hamiltonowski w grafie Mycielskiego

Oznaczenia

Niech ${\displaystyle G}$ oznacza graf, ${\displaystyle V(G)}$ zbiór jego wierzchołków, ${\displaystyle E(G)}$ zbiór krawędzi, ${\displaystyle |A|}$ moc zbioru, ${\displaystyle v_{i}}$ pojedynczy (w tym przypadku ${\displaystyle i}$-ty) wierzchołek grafu, a ${\displaystyle \deg(v)}$ stopień wierzchołka (liczbę kończących się w nim krawędzi). Tradycyjnie oznacza się ${\displaystyle |V(G)|\ =\ n}$ oraz ${\displaystyle |E(G)|\ =\ m,}$ zapis ${\displaystyle \{v,u\}}$ będący zbiorem dwuelementowym wierzchołków, używa się do oznaczenia krawędzi między ${\displaystyle v}$ i ${\displaystyle u}$ (w przypadku digrafów jest to para uporządkowana, gdyż liczy się kolejność oznaczająca kierunek krawędzi).

Indeksowanie wierzchołków

Ścieżka/cykl Hamiltona może być jednoznacznie wyznaczona przez indeksowanie wierzchołków – tj. nadanie im indeksów, powiedzmy ${\displaystyle v_{0},v_{1},\dots ,v_{n},}$ takich, że istnieje ścieżka Hamiltona przechodząca w takiej właśnie kolejności przez wierzchołki grafu.

Gdy znane jest indeksowanie ${\displaystyle v_{0},v_{1},\dots ,v_{n}}$ wyznaczające ścieżkę Hamiltona, to znalezienie (lub potwierdzenie nieistnienia) cyklu Hamiltona jest trywialne i sprowadza się do sprawdzenia, czy istnieje krawędź ${\displaystyle \{v_{n},v_{0}\}}$ – zajmuje to, w zależności od sposobu reprezentacji grafu, czas stały lub ${\displaystyle O(n),}$ gdzie ${\displaystyle n}$ to liczba wierzchołków danego grafu (zobacz: Notacja dużego O).

Warunek konieczny

Jeżeli graf ${\displaystyle G}$ jest hamiltonowski to dla każdego niepustego podzbioru ${\displaystyle V'}$ zbioru wierzchołków ${\displaystyle V(G)}$ zachodzi

${\displaystyle \omega (V(G)\ -\ V')\leqslant |V'|,}$

gdzie ${\displaystyle \omega (G)}$ oznacza liczbę spójnych składowych grafu ${\displaystyle G.}$

Warunki wystarczające

Istnieją jednak twierdzenia pozwalające na podstawie cech grafu, dostępnych w czasie liniowym, stwierdzić jednoznacznie, że dany graf jest hamiltonowski. Należy pamiętać, że jest to implikacja jednostronna – istnieje nieskończenie wiele grafów hamiltonowskich, które nie mają poniższych cech.

Twierdzenia te są matematycznym obrazem dość naturalnej obserwacji dotyczącej własności grafów – jest logiczne, że im więcej jest krawędzi w grafie, tym „większe są szanse” na znalezienie wśród nich drogi Hamiltona. W skrócie (i nieformalnie), poniższe twierdzenia mówią, że graf jest hamiltonowski, jeżeli tylko ma on odpowiednio dużo krawędzi w stosunku do liczby wierzchołków.

Najważniejsze z nich to:

• twierdzenie Diraca (1952),
• twierdzenie Orego (1961),
• twierdzenie o liczbie krawędzi,
• twierdzenie Bondy’ego-Chvátala,
• twierdzenie dla grafu dwudzielnego.

Szczególne przypadki

Oczywiste jest, że żaden graf niespójny nie jest hamiltonowski. Dodawanie krawędzi (w szczególności krawędzi wielokrotnych i pętli) do grafu Hamiltona w oczywisty sposób nie może uczynić z niego grafu niehamiltonowskiego. Każdy graf pełny o ${\displaystyle V}$ wierzchołkach zawiera V! cykli Hamiltona, gdyż dla każdej permutacji indeksów wierzchołków, ${\displaystyle v_{1},v_{2},\dots ,v_{V},v_{1}}$ wyznacza istniejącą drogę, będącą cyklem Hamiltona. Każdy turniej ma ścieżkę Hamiltona.

Algorytmy znajdowania ścieżki Hamiltona

• algorytm Kernighana-Lina
• algorytm mrówkowy
• algorytm Robertsa-Floresa

Zobacz też

• cykl Eulera
• cykl Hamiltona
• graf eulerowski
• łańcuch Eulera
• problem komiwojażera

Przypisy

Bibliografia

• Kenneth Ross, Charles Wright, Matematyka dyskretna, PWN, 2003.
• Robin Wilson, Wprowadzenie do teorii grafów, PWN, 2004.
• Witold Lipski, Kombinatoryka dla programistów, WNT, 2004.
• Karolina Sołtys, „Mrówki, czyli piękno metaheurystyk”.