Sprawdzanie Ścieżki Hamiltona

O Sprawdzanie Ścieżki Hamiltona

Sprawdzanie ścieżki Hamiltona rozstrzyga, czy graf zawiera ścieżkę Hamiltona — sekwencję odwiedzającą każdy wierzchołek dokładnie raz — lub cykl Hamiltona, który dodatkowo powraca do wierzchołka początkowego. Łączy w sobie szybkie wstępne kontrole strukturalne (spójność, wymagania dotyczące stopni, twierdzenie Diraca, twierdzenie Ore) z przeszukiwaniem z nawrotami dostrojonym przez heurystykę Warnsdorffa oraz wizualizuje ścieżkę świadka za pomocą animacji krok po kroku.

Co to jest ścieżka Hamiltona?

Dla danego grafu G = (V, E) o n wierzchołkach, ścieżka Hamiltona to uporządkowana sekwencja v₁, v₂, …, v_n wszystkich wierzchołków taka, że każda kolejna para (v_i, v_i+1) jest krawędzią w G, a każdy wierzchołek pojawia się dokładnie raz. Jeśli dodatkowo (v_n, v₁) jest krawędzią, sekwencja ta jest cyklem Hamiltona.

Problem został nazwany na cześć Williama Rowana Hamiltona, który w 1857 roku wynalazł grę ikozjańską — łamigłówkę polegającą na znalezieniu cyklu odwiedzającego każdy wierzchołek regularnego dwunastościanu dokładnie raz.

Dlaczego to jest trudne: NP-zupełność

Zarówno problem decyzyjny ścieżki Hamiltona, jak i cyklu Hamiltona są NP-zupełne (Karp, 1972). O ile P ≠ NP, nie istnieje algorytm o czasie wielomianowym, który rozwiązywałby każdy przypadek. W najgorszym razie przeszukiwanie z nawrotami bada drzewo o rozmiarze do (n−1)! dla cyklu. Dlatego kalkulator ogranicza dane wejściowe do 20 wierzchołków — niewielki wielomianowy wzrost n powoduje gwałtowny wzrost czasu działania.

W praktyce heurystyka Warnsdorffa (pierwotnie opracowana przez Heinricha Warnsdorffa w 1823 roku dla problemu skoku skoczka) drastycznie przyspiesza wyszukiwanie w grafach strukturalnych: w każdym kroku algorytm rozszerza bieżącą ścieżkę o nieodwiedzonego sąsiada z najmniejszą liczbą pozostałych nieodwiedzonych sąsiadów. Ta zachłanna reguła zapobiega "zapędzeniu się w kozi róg" i często znajduje trasę Hamiltona bez żadnych nawrotów w dobrze zachowujących się grafach.

Warunki konieczne — szybkie odrzucanie

Przed uruchomieniem kosztownego wyszukiwania kalkulator odrzuca grafy, które na pewno nie mogą zawierać ścieżki Hamiltona:

• Spójność. Ścieżka Hamiltona musi odwiedzić każdy wierzchołek, więc graf musi mieć dokładnie jeden spójny komponent. Dla grafów skierowanych wymagana jest słaba spójność (pomijając kierunki strzałek).
• Stopień (nieskierowany). Co najwyżej dwa wierzchołki mogą mieć stopień 1 — są to jedyni kandydaci na końce ścieżki. Dla cyklu Hamiltona każdy wierzchołek musi mieć stopień co najmniej 2.
• Stopień (skierowany). Dla ścieżki Hamiltona co najwyżej jeden wierzchołek może mieć stopień wejściowy 0 (start) i co najwyżej jeden stopień wyjściowy 0 (koniec). Dla cyklu Hamiltona każdy wierzchołek musi mieć stopień wejściowy ≥ 1 oraz stopień wyjściowy ≥ 1.

Zasady te odrzucają wiele beznadziejnych przypadków w czasie liniowym, unikając marnowania wysiłku na przeszukiwanie z nawrotami.

Warunki wystarczające — twierdzenia klasyczne

Kilka klasycznych twierdzeń podaje warunki wystarczające (ale nie konieczne) gwarantujące istnienie cyklu Hamiltona w prostych grafach nieskierowanych. Jeśli którykolwiek z nich ma zastosowanie, kalkulator oznacza wynik jako "GWARANTUJE" bez konieczności uruchamiania wyszukiwania — chociaż nadal pokazuje cykl świadka.

Twierdzenie Diraca (1952)

Jeśli G jest prostym grafem nieskierowanym o n ≥ 3 wierzchołkach i każdy wierzchołek ma stopień co najmniej n / 2, to G posiada cykl Hamiltona.

Twierdzenie Ore (1960)

Jeśli dla każdej pary nieprzyległych wierzchołków u i v mamy deg(u) + deg(v) ≥ n, to G posiada cykl Hamiltona. Warunek Ore jest ściśle słabszy niż Diraca, więc Ore implikuje Diraca.

Niespełnienie warunku Diraca lub Ore nie oznacza, że graf nie ma cyklu Hamiltona — wiele grafów nie spełnia żadnego z nich, a mimo to go zawiera (np. zwykły cykl n-kątny ma minimalny stopień 2, co dla dużych n jest znacznie poniżej n/2).

Algorytm wyszukiwania wewnątrz narzędzia

Gdy wstępne testy nie dają odpowiedzi, kalkulator uruchamia przeszukiwanie z nawrotami na reprezentacji sąsiedztwa grafu. Kluczowe techniki:

1. Maska bitowa zbioru odwiedzonych. Odwiedzone wierzchołki są przechowywane jako maska bitowa (szybki test przynależności O(1) dla maksymalnie 20 wierzchołków).
2. Heurystyka Warnsdorffa. Przy każdym rozszerzeniu sąsiedzi są sprawdzani w kolejności ich pozostałego stopnia nieodwiedzonych wierzchołków (najmniejszy najpierw), naśladując kolejność o "małym rozgałęzieniu".
3. Wybór korzenia. Dla cyklu Hamiltona potrzebny jest tylko jeden wierzchołek startowy (cykle są niezmiennicze względem rotacji). Dla ścieżki Hamiltona starty są próbowane w rosnącej kolejności stopni wyjściowych — najrzadsze pozycje najpierw.
4. Budżet kroków. Sztywny limit zapobiega nieskończonemu działaniu patologicznych przypadków; interfejs zgłasza werdykt jako "timeout", jeśli budżet zostanie wyczerpany.

Hamilton vs Euler

Łatwo pomylić problemy Hamiltona i Eulera — brzmią podobnie, ale są fundamentalnie różne:

Obsługiwane formaty wejściowe

Lista krawędzi

Jedna krawędź na linię lub oddzielona przecinkami. Obsługiwane separatory: A-B, A B, A,B, A--B, A->B, A<-B. Użyj ->, aby wymusić interpretację skierowaną.

Macierz sąsiedztwa

Macierz kwadratowa z wartościami 0/1, jeden wiersz na linię, oddzielona spacjami lub przecinkami. Opcjonalnie podaj etykiety w polu Etykiety macierzy; w przeciwnym razie automatycznie zostaną użyte A, B, C…

Jak korzystać z tego narzędzia

1. Wybierz format wejściowy — Listę krawędzi dla małych, odręcznych grafów lub Macierz sąsiedztwa dla danych wklejonych z kodu lub podręczników.
2. Wklej swój graf w obszarze tekstowym. Dla macierzy możesz opcjonalnie podać etykiety wierzchołków.
3. Wybierz, co sprawdzić: Tylko ścieżkę, tylko cykl lub oba naraz.
4. Wybierz typ grafu — Automatyczne wykrywanie rozpoznaje skierowanie na podstawie stylu strzałek (->) lub symetrii macierzy.
5. Kliknij Sprawdź Hamiltona. Strona wyników pokaże werdykt, wstępne sprawdzenie warunków koniecznych, testy warunków wystarczających Diraca / Ore, ścieżkę świadka (jeśli istnieje) oraz interaktywną wizualizację.
6. Odtwórz świadka za pomocą kontrolek Odtwórz / Krok. Zobacz, jak ścieżka podświetla się krawędź po krawędzi na grafie.

Przykład — Graf Petersena

Słynny graf Petersena (10 wierzchołków, 15 krawędzi, 3-regularny) to podręcznikowy przykład grafu, który posiada ścieżkę Hamiltona, ale nie posiada cyklu Hamiltona. Wklej to w pole listy krawędzi i kliknij Sprawdź:

Narzędzie potwierdza: znaleziono ścieżkę Hamiltona (np. 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), ale wyczerpujące wyszukiwanie nie znajduje sposobu na zamknięcie pętli — wynik ten został po raz pierwszy udowodniony w latach 90. XIX wieku.

Typowe zastosowania

• Logistyka i Problem Komiwojażera (TSP) — każda trasa TSP jest cyklem Hamiltona w kompletnym grafie ważonym.
• Montaż genomu — rekonstrukcja sekwencji DNA z nakładających się odczytów może być modelowana jako ścieżka Hamiltona w grafie nakładania się.
• Projektowanie obwodów — rozmieszczanie pinów na płytce PCB w celu uzyskania minimalnej długości przewodów.
• AI w grach i rozwiązywanie zagadek — trasy skoczka na szachownicy, gra ikozjańska.
• Harmonogramowanie — sekwencjonowanie zadań tak, aby każde przejście między nimi było wykonalne.
• Dydaktyka kombinatoryki — ilustrowanie NP-zupełności na małych przykładach możliwych do rozwiązania ręcznie.

Najczęściej zadawane pytania

Co to jest ścieżka Hamiltona?

Ścieżka Hamiltona to droga w grafie, która odwiedza każdy wierzchołek dokładnie raz. Nazwa pochodzi od Williama Rowana Hamiltona, który badał ten problem na grafie dwunastościanu w 1857 roku. Rozstrzygnięcie, czy taka ścieżka istnieje, jest problemem NP-zupełnym, więc żaden znany algorytm nie rozwiązuje go w czasie wielomianowym dla wszystkich grafów.

Czym różni się cykl Hamiltona od ścieżki Hamiltona?

Cykl Hamiltona to ścieżka Hamiltona, która powraca do swojego wierzchołka początkowego, tworząc zamkniętą pętlę odwiedzającą każdy wierzchołek dokładnie raz. Każdy cykl Hamiltona zawiera ścieżkę Hamiltona (wystarczy usunąć krawędź zamykającą), ale odwrotna zależność nie zachodzi: wiele grafów ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.

Co mówi twierdzenie Diraca?

Twierdzenie Diraca (1952) stwierdza, że każdy prosty graf nieskierowany o n ≥ 3 wierzchołkach, w którym każdy wierzchołek ma stopień co najmniej n/2, zawiera cykl Hamiltona. Jest to warunek wystarczający, ale nie konieczny: wiele grafów, które nie spełniają progu Diraca, nadal posiada cykle Hamiltona.

Co mówi twierdzenie Ore?

Twierdzenie Ore (1960) stwierdza, że jeśli dla każdej pary nieprzyległych wierzchołków u i v w prostym grafie o n ≥ 3 wierzchołkach suma ich stopni wynosi co najmniej n, to graf posiada cykl Hamiltona. Warunek Ore jest słabszy niż Diraca, więc twierdzenie Ore ma zastosowanie wszędzie tam, gdzie twierdzenie Diraca.

Dlaczego wyszukiwanie jest ograniczone do 20 wierzchołków?

Problemy decyzyjne dotyczące ścieżki i cyklu Hamiltona są NP-zupełne. W najgorszym przypadku czas działania rośnie wykładniczo wraz z liczbą wierzchołków. Dzięki przycinaniu i heurystyce Warnsdorffa kalkulator szybko radzi sobie z wieloma małymi grafami do 20 wierzchołków, ale trudniejsze przypadki mogą przekroczyć limit czasu. Powyżej 20 wierzchołków należy używać specjalistycznych solverów, takich jak Concorde, lub sformułowań programowania całkowitoliczbowego.

Co to jest heurystyka Warnsdorffa?

Reguła Warnsdorffa, zaproponowana w 1823 roku dla problemu skoku skoczka szachowego, mówi, że w każdym kroku należy odwiedzić następny wierzchołek, który ma najmniej pozostałych nieodwiedzonych sąsiadów. Ta zachłanna reguła w praktyce radykalnie przycina drzewo nawrotów i często znajduje ścieżki Hamiltona bez żadnych nawrotów w grafach regularnych.

Czy to narzędzie znajduje wszystkie ścieżki Hamiltona?

Nie — znajduje jedną ścieżkę świadka lub cykl, jeśli takowy istnieje. Liczenie całkowitej liczby ścieżek Hamiltona jest samo w sobie problemem #P-zupełnym i znacznie trudniejszym niż sam problem decyzyjny. Do enumeracji bardziej odpowiednie są specjalistyczne narzędzia lub solvery programowania całkowitoliczbowego.

Dalsza lektura

• Ścieżka Hamiltona — Wikipedia (EN)
• Problem ścieżki Hamiltona — Wikipedia (EN)
• Twierdzenie Diraca o cyklach Hamiltona — Wikipedia (EN)
• Twierdzenie Ore — Wikipedia (EN)
• Reguła Warnsdorffa — Wikipedia (EN)

Inne powiązane narzędzia:

Zaawansowane działania matematyczne:

• Kalkulator Antylogarytmów
• Kalkulator funkcji beta
• Kalkulator współczynnika dwumianu
• Kalkulator rozkładu dwumianowego Polecane
• Kalkulator Bitowy
• Kalkulator Twierdzenia Centralnego Granicznego
• Kalkulator kombinacji
• Komplementarny kalkulator funkcji błędu
• Kalkulator liczb zespolonych
• Kalkulator Entropii
• Kalkulator funkcji błędu
• Kalkulator rozkładu wykładniczego
• Kalkulator wzrostu wykładniczego - wysoka precyzja
• Kalkulator całki wykładniczej
• kalkulator-wykładników-wysoka-precyzja
• Kalkulator silni
• Kalkulator Funkcji Gamma
• Kalkulator złotego podziału
• Kalkulator półtrwania
• Kalkulator tempa wzrostu procentowego
• Kalkulator permutacji
• Kalkulator Rozkładu Poissona
• Kalkulator korzeni wielomianów ze szczegółowymi krokami
• Kalkulator prawdopodobieństwa
• Kalkulator rozkładu prawdopodobieństwa
• Kalkulator Proporcji
• Kalkulator Formuły Kwadratowej
• Kalkulator Naukowy Polecane
• Kalkulator notacji naukowej
• Kalkulator Cyfr Znaczących Nowy
• Kalkulator sumy sześcianów
• Kalkulator sumy kolejnych liczb
• Kalkulator sumy kwadratów
• Generator tablicy prawdy Nowy
• Kalkulator teorii zbiorów Nowy
• Generator Diagramu Venna (3 zbiory) Nowy
• Kalkulator chińskiego twierdzenia o resztach Nowy
• Kalkulator Funkcji Tocjenta Eulera Nowy
• Kalkulator rozszerzonego algorytmu Euklidesa Nowy
• Kalkulator modularnej odwrotności multiplikatywnej Nowy
• Kalkulator ułamków łańcuchowych Nowy
• Kalkulator Najkrótszej Ścieżki Dijkstry Nowy
• Kalkulator Minimalnego Drzewa Rozpinającego Nowy
• Walidator ciągu stopni grafu Nowy
• Kalkulator Nieporządków (Podfaktoriał) Nowy
• Kalkulator liczb Stirlinga Nowy
• Kalkulator Zasady Szufladkowej Nowy
• Kalkulator rozkładu stacjonarnego łańcucha Markowa Nowy
• Kalkulator Zaokrąglania Nowy
• Kalkulator Rozkładu Ujemnego Dwumianowego Nowy
• Kalkulator Permutacji z Powtórzeniami Nowy
• Kalkulator Potęgowania Modularnego Nowy
• Kalkulator Pierwiastka Pierwotnego Nowy
• Upraszczacz Algebry Boole’a Nowy
• Solver Tablicy Karnaugha (K-Map) Nowy
• Kalkulator Kolorowania Grafów Nowy
• Kalkulator Sortowania Topologicznego Nowy
• Kalkulator Macierzy Sąsiedztwa Nowy
• Kalkulator Włączeń i Wyłączeń Nowy
• Solver Programowania Liniowego Nowy
• Solver Problemu Komiwojażera (TSP) Nowy
• Sprawdzanie Ścieżki Hamiltona Nowy