Ścieżki i cykle Hamiltona wyjaśnione
Narysuj pięć kropek w kółku, połącz każdą z dwiema sąsiednimi i możesz obejść każdą kropkę raz i wrócić do domu: to cykl Hamiltona. Dodaj kilka krawędzi albo usuń kilka, a pytanie staje się zaskakująco trudne. To, czy graf ma taki cykl, należy do najbardziej znanych problemów, na które żaden komputer nie umie jeszcze szybko odpowiedzieć dla każdego grafu.
Każdy wierzchołek raz
Graf to zbiór punktów, wierzchołków, połączonych liniami, krawędziami. Ścieżka Hamiltona biegnie po krawędziach i odwiedza każdy wierzchołek dokładnie raz; cykl Hamiltona wraca dodatkowo tam, gdzie się zaczął, więc ma tyle samo krawędzi co wierzchołków. Graf z cyklem Hamiltona nazywamy hamiltonowskim. Sprawdzenie proponowanej trasy jest łatwe: policz wierzchołki i obejrzyj każdy krok. Znalezienie jej albo wykazanie, że żadnej nie ma, to część trudna, bo liczba kolejności, w jakich można odwiedzić wierzchołki, rośnie jak n!, przy 20 wierzchołkach już 2,4 × 10¹⁸.
Gra ikozjańska Hamiltona
William Rowan Hamilton, irlandzki matematyk, który odkrył kwaterniony, wymyślił grę ikozjańską w 1857 roku. Jej plansza pokazywała dwunastościan spłaszczony na płaszczyźnie, z 20 wierzchołkami oznaczonymi spółgłoskami, a głównym zadaniem było ustawić kołki z numerami od 1 do 20 na wierzchołkach tak, by kolejne liczby, a także 20 i 1, łączyła krawędź. Hamilton sprzedał prawa za 25 funtów londyńskiemu wytwórcy zabawek John Jaques and Son, który wydał grę w 1859 roku; sprzedawała się słabo. Łamigłówka ma 30 rozwiązań, licząc cykl raz niezależnie od startu i kierunku. Samo pytanie nie było nowe: Thomas Kirkman w pracy wysłanej do Royal Society w 1855 roku pytał, które wielościany mają cykl przez wszystkie wierzchołki, i pokazał taki, który go nie ma.
Trasy skoczka
Trasa skoczka prowadzi szachowego skoczka tak, by stanął na każdym polu dokładnie raz: to ścieżka Hamiltona w grafie, którego wierzchołkami są pola, a krawędziami ruchy skoczka. Trasa zamknięta kończy się o skok skoczka od startu, czyli jest cyklem Hamiltona. Szachiści układali takie zadania ponad tysiąc lat temu, a Euler badał je w pracy z 1759 roku. W 1823 roku H. C. von Warnsdorff zaproponował, by zawsze iść na pole o najmniejszej liczbie dalszych ruchów; ta prosta reguła zwykle kończy trasę po szachownicy 8 × 8 bez cofania. Skoczek zawsze zmienia kolor pola, więc trasa zamknięta potrzebuje tyle samo pól jasnych co ciemnych, co wyklucza szachownice o nieparzystej liczbie pól. Allen Schwenk pokazał w 1991 roku dokładnie, które prostokątne szachownice mają trasę zamkniętą; wśród kwadratowych ma ją każda o parzystym boku co najmniej 6. Zwykła szachownica ma 13 267 364 410 532 trasy zamknięte, policzone przez Brendana McKaya w 1997 roku.
Grafy bez cyklu Hamiltona
Najszybsze dowody, że cyklu nie ma, to argumenty zliczające. Jeśli wierzchołki można pokolorować dwoma kolorami tak, by każda krawędź łączyła różne kolory, cykl się przeplata i potrzebuje tylu samo wierzchołków każdego koloru; siatka 5 × 5 ma 13 jednego i 12 drugiego, więc nie ma cyklu Hamiltona. Punkt artykulacji, którego usunięcie rozrywa graf, musiałby być przechodzony dwa razy, a wierzchołek stopnia 1 nie może być przechodzony wcale. Niektóre grafy wymykają się wszystkim takim argumentom. Graf Petersena, opublikowany przez Juliusa Petersena w 1898 roku, ma 10 wierzchołków stopnia 3 i nie ma cyklu Hamiltona, a mimo to usunięcie dowolnego wierzchołka zostawia graf, który go ma; jest najmniejszym takim grafem hipohamiltonowskim. Graf Herschela, nazwany po Alexandrze Stewarcie Herschelu, który pisał o grze ikozjańskiej w 1862 roku, ma 11 wierzchołków i 18 krawędzi i jest grafem wielościanu o dziewięciu czworokątnych ścianach. Żadnemu wielościanowi o mniejszej liczbie wierzchołków nie brakuje cyklu Hamiltona. W 1884 roku Peter Guthrie Tait postawił hipotezę, że każdy wielościan mający trzy krawędzie w każdym wierzchołku go ma; W. T. Tutte znalazł w 1946 roku kontrprzykład o 46 wierzchołkach.
Warunki, które go gwarantują
Jeśli graf ma wiele krawędzi, cykl Hamiltona jest pewny. Gabriel Dirac udowodnił w 1952 roku, że graf o n ≥ 3 wierzchołkach, w którym każdy wierzchołek ma stopień co najmniej n/2, go ma, a Øystein Ore osłabił ten warunek w 1960 roku: wystarczy, by dwa niepołączone wierzchołki miały zawsze stopnie o sumie co najmniej n. Oba warunki działają tylko w jedną stronę. Zwykły pierścień o 100 wierzchołkach ma wszędzie stopień 2, daleko poniżej 50, a mimo to jest cyklem Hamiltona. Tak wygląda obraz ogólny: są warunki wystarczające i są powody niepowodzenia, a między nimi rozciąga się wielki obszar grafów, o których rozstrzygnąć może tylko szukanie.
Dlaczego nie znamy szybkiego testu
Rozstrzygnięcie, czy graf ma cykl Hamiltona, jest NP-zupełne; to był jeden z 21 problemów z listy Richarda Karpa z 1972 roku. Metoda rozwiązująca go szybko dla każdego grafu rozwiązałaby szybko tysiące innych problemów i rozstrzygnęłaby pytanie P wobec NP. Kontrast ze ścieżkami Eulera, które używają każdej krawędzi raz, jest uderzający: Euler pokazał w 1736 roku, że policzenie wierzchołków nieparzystego stopnia rozstrzyga tamto pytanie od razu. Najlepsze metody dokładne dla cykli Hamiltona wciąż wymagają czasu wykładniczego. Programowanie dynamiczne po wszystkich podzbiorach wierzchołków, znalezione przez Richarda Bellmana oraz przez Michaela Helda i Richarda Karpa w 1962 roku, wymaga około n² × 2ⁿ kroków, a losowa metoda Andreasa Björklunda z 2010 roku około 1,657ⁿ. W praktyce nawroty z dobrym odcinaniem radzą sobie z grafami o kilkudziesięciu wierzchołkach, a problem komiwojażera, który szuka najkrótszego cyklu Hamiltona, jest ważoną wersją tego samego pytania.
Kody Graya i hipersześcian
Zapisz liczby od 0 do 7 jako kody 3-bitowe i połącz dwa kody, gdy różnią się dokładnie jednym bitem: wynikiem jest graf sześcianu. Cykl Hamiltona w nim, na przykład 000, 001, 011, 010, 110, 111, 101, 100, wymienia wszystkie osiem kodów tak, że każdy różni się od poprzedniego jednym bitem. Taka lista to kod Graya, nazwany po Franku Grayu z Bell Labs, który opisał go w patencie zgłoszonym w 1947 roku. Każdy hipersześcian go ma: zapisz kody o jeden bit krótsze, potem tę samą listę wspak, i dopisz 0 przed pierwszą połową, a 1 przed drugą. Enkodery obrotowe używają kodów Graya, by odczyt między dwoma położeniami nigdy nie mylił się o więcej niż jeden krok. Sześcian ma 6 cykli Hamiltona, a hipersześcian 4-bitowy 1344.
Sprawdź sam
Otwórz eksplorator ścieżek Hamiltona, aby samemu spróbować łamigłówki Hamiltona, z przerywanymi okręgami pokazującymi, dokąd możesz pójść, albo przejdź do trybu Szukanie i popatrz, jak pracują nawroty: ścieżka rośnie, czerwone kreski znaczą miejsca zawrócenia, a słupki liczą węzły według długości ścieżki. Włączaj i wyłączaj kontrolę ślepych zaułków, kontrolę spójności i kolejność Warnsdorffa, porównaj, ile węzłów potrzebuje każda, policz wszystkie cykle małego grafu albo narysuj własny graf i zobacz, które z szybkich testów działają.
Często zadawane pytania
Czy graf z obwodem Eulera jest też hamiltonowski, albo odwrotnie?
Żadne nie wynika z drugiego. Muszka, dwa trójkąty o wspólnym wierzchołku, ma obwód Eulera, bo każdy stopień jest parzysty, ale nie ma cyklu Hamiltona, bo wspólny wierzchołek musiałby być przechodzony dwa razy. Graf pełny K₄ ma cykle Hamiltona, ale wszystkie cztery wierzchołki mają stopień 3, więc nie ma obwodu Eulera.
Czy komputer nie może po prostu sprawdzić wszystkich kolejności?
Tylko dla małych grafów. Kolejności n wierzchołków jest n!, dla 20 około 2,4 × 10¹⁸. Nawroty radzą sobie znacznie lepiej, bo idą tylko po krawędziach i porzucają ścieżkę częściową, gdy tylko utkną: znajdują wszystkie 30 cykli dwudziestowierzchołkowego dwunastościanu w około 1400 krokach. Ale dla niektórych grafów liczba ścieżek częściowych i tak rośnie wykładniczo, a nie znamy metody, która unika tego dla każdego grafu.
Czy problem ścieżki Hamiltona jest łatwiejszy niż problem cyklu?
Nie, oba są NP-zupełne. Każdy można przełożyć na drugi: dodaj nowy wierzchołek połączony z każdym starym, a stary graf ma ścieżkę Hamiltona dokładnie wtedy, gdy nowy ma cykl Hamiltona. W drugą stronę problem cyklu staje się problemem ścieżki, gdy dodamy kopię jednego wierzchołka, o tych samych sąsiadach, i doczepimy nowy wierzchołek końcowy do wierzchołka, a drugi do jego kopii.
Dlaczego trasa skoczka na szachownicy 5 × 5 musi zaczynać się na kolorze narożników?
Spośród 25 pól 13 ma kolor narożników, a 12 drugi, a skoczek zmienia kolor przy każdym ruchu. Trasa po 25 polach przeplata kolory, więc zaczyna się i kończy na kolorze, który ma więcej pól. Aplikacja znajduje wszystkie 1728 tras otwartych szachownicy 5 × 5, czyli 864, gdy trasę i jej odwrotność liczyć raz, i każda zaczyna się i kończy na polu w kolorze narożników.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz eksplorator ścieżek Hamiltona