Ścieżka
Zbadane węzły
Cykl Hamiltona
Ścieżka Hamiltona

Tryb

    Cel

    Więcej o ścieżkach i cyklach Hamiltona

    Eksplorator ścieżek Hamiltona

    W 1857 roku William Rowan Hamilton wymyślił łamigłówkę: przejść po krawędziach dwunastościanu tak, by minąć każdy z jego 20 wierzchołków dokładnie raz i skończyć tam, gdzie się zaczęło. Taką trasę nazywamy dziś cyklem Hamiltona. Łatwo ją sprawdzić i na ogół trudno znaleźć. Narysuj ją sam na dwunastościanie Hamiltona, na szachownicy albo na grafie, który narysujesz, albo popatrz, jak przeszukiwanie z nawrotami jej szuka, policz ślepe zaułki, w które wpada, i zobacz, jak bardzo kilka prostych kontroli skraca szukanie. Wybierz graf i cel: cykl wracający do punktu wyjścia albo ścieżkę. Rysowanie: kliknij wierzchołek, aby zacząć, potem po kolei sąsiadów; przerywane okręgi pokazują, dokąd możesz pójść. Kliknięcie ostatniego wierzchołka, Wstecz lub Cofnij cofa o krok, a Podpowiedź wskazuje następny krok, który wciąż da się dokończyć. Szukanie: Uruchom albo Krok prowadzi przeszukiwanie z nawrotami, które dokłada wierzchołki, aż utknie, i wtedy się cofa; czerwone kreski pokazują nawroty, a słupki liczą węzły według długości ścieżki. Przed startem kliknięcie wierzchołka wybiera, gdzie się zaczyna. Pola wyboru włączają i wyłączają odcinanie, Porównaj uruchamia to samo szukanie z nim i bez niego, a Policz wszystkie liczy każdy cykl lub każdą ścieżkę małego grafu. Edycja: kliknij, aby dodać wierzchołek, kliknij dwa wierzchołki, aby je połączyć lub rozłączyć, przeciągnij, aby przesunąć jeden, a Usuń kasuje wybrany wierzchołek.

    Jak to działa

    1. Wybierz graf, na przykład dwunastościan Hamiltona, graf Petersena albo trasę skoczka, albo narysuj własny w Edycji, i wybierz jako cel cykl lub ścieżkę.
    2. W trybie Rysowanie kliknij wierzchołek, aby zacząć, a potem kolejnych sąsiadów. Wstecz i Cofnij cofają o krok, a Podpowiedź pokazuje następny krok, który wciąż da się dokończyć.
    3. W trybie Szukanie naciśnij Uruchom albo Krok, aby patrzeć, jak nawroty szukają trasy, włączaj i wyłączaj odcinanie, i naciśnij Porównaj, aby zobaczyć, ile węzłów potrzebuje każda wersja.

    Hamilton a Euler

    Ścieżka Eulera używa każdej krawędzi raz; ścieżka Hamiltona odwiedza każdy wierzchołek raz. Brzmi podobnie, ale zachowuje się zupełnie inaczej. To, czy graf spójny ma ścieżkę Eulera, rozstrzyga się przez policzenie wierzchołków nieparzystego stopnia, jak pokazał Euler w 1736 roku: ma ją, gdy nie ma takich wierzchołków albo są dwa. Dla ścieżek Hamiltona nie znamy takiej reguły. Rozstrzygnięcie, czy graf ma cykl Hamiltona, jest NP-zupełne, to jeden z 21 problemów z listy Richarda Karpa z 1972 roku, więc szybka metoda dla niego dałaby szybkie metody dla tysięcy innych trudnych problemów. Istnieją za to warunki rozstrzygające dla części grafów. Twierdzenie Diraca z 1952 roku gwarantuje cykl Hamiltona, gdy każdy wierzchołek ma stopień co najmniej n/2, a twierdzenie Orego z 1960 roku, gdy dwa niepołączone wierzchołki mają zawsze stopnie o sumie co najmniej n; wierzchołek stopnia 1, punkt artykulacji albo dwie klasy kolorów o różnej liczebności go wykluczają.

    Jak działa szukanie

    Przeszukiwanie z nawrotami buduje ścieżkę po jednym wierzchołku i, gdy utknie, cofa ostatni krok i próbuje następnego sąsiada. Zawsze znajdzie cykl Hamiltona, jeśli taki istnieje, ale liczba ścieżek częściowych może rosnąć wykładniczo. Na siatce 5 × 5, która nie ma cyklu Hamiltona, zwykłe nawroty badają 153 745 węzłów, zanim nabiorą pewności. Dwie kontrole wcześnie zatrzymują beznadziejne ścieżki: nieodwiedzony wierzchołek mający mniej niż dwóch wolnych sąsiadów nie zmieści się już w cyklu, a gdy nieodwiedzone wierzchołki rozpadną się na osobne części, żadna pojedyncza ścieżka ich nie pokryje. Z obiema ten sam dowód zajmuje 1761 węzłów. Reguła Warnsdorffa z 1823 roku, która próbuje najpierw sąsiada z najmniejszą liczbą dalszych ruchów, znajduje trasę skoczka na 8 × 8 z narożnika w 64 ruchach bez ani jednego ślepego zaułka.

    Często zadawane pytania

    Jaka jest różnica między ścieżką Hamiltona a cyklem Hamiltona?

    Ścieżka Hamiltona odwiedza każdy wierzchołek grafu dokładnie raz. Cykl Hamiltona robi to samo, a potem wraca jedną dodatkową krawędzią tam, gdzie się zaczął, więc może zacząć się w dowolnym ze swoich wierzchołków. Każdy graf z cyklem Hamiltona ma ścieżkę Hamiltona (wystarczy pominąć jedną krawędź cyklu), ale nie odwrotnie: graf Petersena ma ścieżki Hamiltona i nie ma cyklu Hamiltona.

    Czy dwunastościan ma cykl Hamiltona?

    Tak, 30, licząc każdy cykl raz niezależnie od startu i kierunku. Hamilton zamienił to w 1857 roku w grę ikozjańską, planszę z 20 wierzchołkami spłaszczonego dwunastościanu oznaczonymi spółgłoskami, i sprzedał prawa za 25 funtów londyńskiemu wytwórcy zabawek John Jaques and Son. Policz wszystkie znajduje te 30 cykli w około 1400 węzłach.

    Dlaczego siatka 5 × 5 nie ma cyklu Hamiltona?

    Pokoloruj 25 punktów jak szachownicę: 13 dostaje jeden kolor, a 12 drugi, i każdy krok prowadzi do drugiego koloru. Cykl przeplata kolory przez cały obieg, więc potrzebuje tyle samo jednego co drugiego, czego 13 i 12 nie dają. Ten sam argument działa dla każdej siatki o nieparzystej liczbie punktów, dla skoczka na szachownicy 5 × 5 lub 7 × 7 (skoczek zawsze zmienia kolor pola) oraz dla grafu Herschela, którego dwie klasy mają 6 i 5 wierzchołków. Ścieżka Hamiltona pozostaje możliwa: zaczyna się i kończy na liczniejszym kolorze.

    Jak reguła Warnsdorffa znajduje trasę skoczka?

    H. C. von Warnsdorff zaproponował w 1823 roku, by zawsze przestawiać skoczka na pole, z którego będzie miał najmniej dalszych ruchów. Pola przy brzegach i w narożnikach, łatwe do odcięcia, są dzięki temu odwiedzane wcześnie, póki skoczek jeszcze może do nich wejść. Reguła jest praktyczna, nie daje gwarancji, a remisy trzeba jakoś rozstrzygać, ale na szachownicy 8 × 8 zwykle kończy trasę bez cofania. Połączona z nawrotami, jak w tej aplikacji, znajduje trasy otwarte od 5 × 5 wzwyż i trasy zamknięte na szachownicach 6 × 6 i 8 × 8.

    Ile cykli Hamiltona ma graf pełny?

    (n − 1)!/2 dla n ≥ 3. Ustal wierzchołek startowy; pozostałe n − 1 może następować w dowolnej kolejności, a każdy cykl liczony jest dwa razy, raz w każdym kierunku. K₆ ma 5!/2 = 60, a K₁₀ ma 181 440. To właśnie trasy, spośród których musi wybierać komiwojażer, i dlatego sprawdzanie ich wszystkich tak szybko przestaje być możliwe.

    Chcesz wypróbować?

    Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

    Przejdź do edytora