Graf hamiltonowski

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

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.

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”.