Cykl Hamiltona

Słowniczek pojęć kluczowych

Cykl Hamiltona – to specjalna trasa w grafie, która pozwala odwiedzić każdy punkt (wierzchołek) dokładnie jeden raz i wrócić bezpiecznie do miejsca startu. Można to porównać do planowania wycieczki po miastach tak, by w żadnym nie być dwa razy, ale ostatecznie wrócić do domu.
Ścieżka Hamiltona – jest bardzo podobna do cyklu, ale nie wymaga powrotu do punktu początkowego. Kończymy naszą podróż w innym miejscu, niż zaczęliśmy, upewniając się jedynie, że zaliczyliśmy wszystkie zaplanowane przystanki.
Graf – to matematyczna mapa składająca się z punktów (wierzchołków) oraz linii (krawędzi), które je łączą. Grafy służą do modelowania wszystkiego: od połączeń lotniczych, przez sieci społecznościowe, aż po układy scalone w komputerach.
Wierzchołek – to pojedynczy punkt na mapie grafu, który reprezentuje konkretny obiekt, np. miasto, serwer w sieci lub osobę. W kontekście cyklu Hamiltona to właśnie te punkty musimy „odwiedzić”.
Krawędź – to linia łącząca dwa wierzchołki, oznaczająca bezpośrednie połączenie lub drogę między nimi. Jeśli między dwoma miastami nie ma krawędzi, nie możemy przejechać bezpośrednio z jednego do drugiego.
Stopień wierzchołka – to prosta liczba mówiąca nam, ile dróg (krawędzi) wychodzi z danego punktu. Im wyższy stopień, tym więcej mamy opcji ucieczki lub wjazdu do danego miejsca.
Graf hamiltonowski – to taki graf, w którym w ogóle da się wyznaczyć cykl Hamiltona. Nie każda sieć dróg pozwala na taką podróż, więc znalezienie tej cechy jest dla matematyków bardzo cenne.
NP-zupełność – to termin określający problemy „bardzo trudne” dla komputerów. Oznacza, że znalezienie rozwiązania (cyklu) w ogromnej sieci może zająć współczesnym maszynom nawet miliony lat.
Algorytm z nawrotami (Backtracking) – to metoda szukania drogi polegająca na sprawdzaniu ścieżki „na oślep”, a gdy trafimy w ślepy zaułek – cofaniu się do ostatniego skrzyżowania. Jest to skuteczna, ale bardzo powolna metoda przeszukiwania grafu.
Problem komiwojażera (TSP) – to słynne zadanie praktyczne, w którym szukamy najkrótszego (najtańszego) cyklu Hamiltona. Handlowiec chce odwiedzić wszystkich klientów przy najmniejszym zużyciu paliwa.
Graf pełny – to idealnie połączona sieć, w której z każdego punktu można bezpośrednio przejść do każdego innego. W takim grafie znalezienie cyklu Hamiltona jest dziecinnie proste, bo dróg jest pod dostatkiem.
Twierdzenie Diraca – to matematyczna zasada mówiąca, że jeśli każdy punkt ma odpowiednio dużo połączeń (minimum połowę liczby wszystkich punktów), to cykl Hamiltona na pewno istnieje. To swoista „gwarancja gęstości” sieci.
Spójność grafu – to cecha oznaczająca, że graf nie jest rozbity na oddzielne, niepołączone ze sobą „wyspy”. Jeśli graf jest niespójny, nigdy nie uda nam się odwiedzić wszystkich punktów w jednej podróży.
Graf planarny – to taki graf, który można narysować na kartce papieru tak, aby żadne drogi (krawędzie) nie przecinały się nad sobą jak wiadukty. Przypomina to płaską mapę narysowaną bez odrywania ołówka.
Domknięcie grafu – to technika „dorysowywania” brakujących dróg do grafu w celu sprawdzenia, czy stanie się on łatwiejszy do analizy. Pomaga matematykom udowodnić istnienie cyklu w skomplikowanych i rzadkich sieciach.

1. Definicja i podstawy teorii grafów hamiltonowskich

Konstrukcja cyklu Hamiltona opiera się na pojęciu podgrafu spinającego, który musi być cyklem. Formalnie, dla grafu prostego $G = (V, E)$ , gdzie $V = {v_1, v_2, \dots, v_n}$ jest zbiorem wierzchołków o liczności $|V| = n$ , a $E \subseteq {{u, v} : u, v \in V, u \neq v}$ jest zbiorem krawędzi, cykl Hamiltona definiujemy jako ciąg wierzchołków $(v_{i_1}, v_{i_2}, \dots, v_{i_n}, v_{i_1})$ . W ciągu tym każdy wierzchołek $v \in V$ występuje dokładnie jeden raz, poza wierzchołkiem startowym i końcowym, które są tożsame. Istnienie takiego ciągu implikuje, że dla każdego $j \in {1, \dots, n-1}$ krawędź ${v_{i_j}, v_{i_{j+1}}}$ należy do zbioru $E$ , a także ${v_{i_n}, v_{i_1}} \in E$ . Jeśli graf $G$ posiada przynajmniej jeden taki cykl, relacja ta klasyfikuje go jako graf hamiltonowski, co matematycznie oznacza, że $G$ zawiera podgraf izomorficzny z grafem cyklicznym $C_n$ .

Ważnym rozróżnieniem w teorii struktur jest pojęcie ścieżki Hamiltona, która jest słabszą formą tego zagadnienia. Ścieżka Hamiltona to prosta ścieżka w grafie $G$ , która przechodzi przez każdy wierzchołek $v \in V$ dokładnie raz, ale nie wymaga istnienia krawędzi domykającej ${v_{i_n}, v_{i_1}}$ . Graf posiadający ścieżkę Hamiltona, lecz nieposiadający cyklu Hamiltona, nazywany jest grafem półhamiltonowskim. Zbiór wszystkich cykli Hamiltona w grafie pełnym $K_n$ jest liczny i wynosi dokładnie $\frac{(n-1)!}{2}$ , co ukazuje skalę trudności przy próbie enumeracji takich struktur w grafach o dużej gęstości. Warto zauważyć, że stopień wierzchołka $d(v)$ odgrywa tu kluczową rolę, gdyż w każdym cyklu Hamiltona każdy wierzchołek musi mieć stopień co najmniej $2$ w ramach tego podgrafu, co prowadzi do wniosku, że graf o minimalnym stopniu $\delta(G) < 2$ nie może być hamiltonowski.

Analiza strukturalna grafów pod kątem własności Hamiltona często odwołuje się do macierzy sąsiedztwa $A$ , gdzie $A_{ij} = 1$ , gdy ${v_i, v_j} \in E$ , oraz $A_{ij} = 0$ w przeciwnym razie. Chociaż nie istnieje prosta niezmiennicza macierzowa determinująca hamiltonowskość, to liczba ścieżek o długości $k$ między wierzchołkami może być wyznaczona przez $k$ -tą potęgę macierzy $A^k$ . Problem znalezienia cyklu Hamiltona sprowadza się do znalezienia takiej permutacji $\sigma$ zbioru indeksów ${1, \dots, n}$ , dla której iloczyn elementów macierzy $A_{\sigma(1)\sigma(2)} A_{\sigma(2)\sigma(3)} \dots A_{\sigma(n)\sigma(1)} = 1$ . Ta kombinatoryczna definicja podkreśla, dlaczego problem ten jest obliczeniowo trudny, gdyż liczba możliwych permutacji rośnie silniowo wraz z rzędem grafu $n$ .

Dodatkowym aspektem jest relacja między hamiltonowskością a spójnością grafu. Każdy graf hamiltonowski musi być co najmniej 2-spójny wierzchołkowo, co oznacza, że usunięcie dowolnego jednego wierzchołka $v \in V$ nie powoduje utraty spójności grafu, czyli $\kappa(G) \geq 2$ . Warunek ten jest konieczny, ponieważ w cyklu Hamiltona istnieją zawsze co najmniej dwie rozłączne wierzchołkowo ścieżki między dowolną parą wierzchołków $u, v$ . W ujęciu bardziej ogólnym, jeśli graf jest hamiltonowski, to dla każdego niepustego podzbioru $S \subset V$ liczba składowych spójnych grafu $G - S$ , oznaczana jako $\omega(G - S)$ , musi spełniać nierówność $\omega(G - S) \leq |S|$ . Złamanie tej zasady dla jakiegokolwiek zbioru $S$ jest natychmiastowym dowodem na brak cyklu Hamiltona w danej strukturze.

2. Złożoność obliczeniowa i problem decyzyjny

Problem decyzyjny dotyczący istnienia cyklu Hamiltona, oznaczany często jako $\text{HC}$ (Hamiltonian Cycle), polega na rozstrzygnięciu, czy dla danego grafu nieskierowanego $G = (V, E)$ istnieje podzbiór krawędzi $E' \subseteq E$ , który tworzy cykl prosty przechodzący przez każdy wierzchołek $v \in V$ . Z punktu widzenia teorii złożoności obliczeniowej, problem ten zajmuje centralne miejsce, będąc jednym z 21 problemów NP-zupełnych Richarda Karpa. Przynależność do klasy $\text{NP}$ jest łatwa do wykazania, ponieważ certyfikat w postaci uporządkowanej sekwencji wierzchołków $(v_1, v_2, \dots, v_n)$ może zostać zweryfikowany w czasie wielomianowym $O(n)$ , sprawdzając jedynie, czy każda para ${v_i, v_{i+1}}$ oraz ${v_n, v_1}$ jest krawędzią w $E$ . Dowód NP-zupełności opiera się na redukcji wielomianowej z problemu spełnialności formuł logicznych $\text{3-SAT} \leq_P \text{HC}$ , co oznacza, że dowolną instancję problemu $\text{3-SAT}$ można przekształcić w graf, w którym istnienie cyklu Hamiltona odpowiada istnieniu wartościowania spełniającego daną formułę.

Relacja między problemem Hamiltona a problemem komiwojażera, znanym jako $\text{TSP}$ (Traveling Salesperson Problem), jest fundamentalna dla optymalizacji dyskretnej. Problem $\text{HC}$ można postrzegać jako szczególny przypadek $\text{TSP}$ , w którym wagi krawędzi $w(e)$ są zdefiniowane jako $1$ dla krawędzi istniejących w grafie i $\infty$ (lub dostatecznie duża liczba $M$ ) dla krawędzi nieistniejących. Wówczas graf posiada cykl Hamiltona wtedy i tylko wtedy, gdy rozwiązanie problemu $\text{TSP}$ dla grafu pełnego $K_n$ z tak zdefiniowanymi wagami ma całkowitą długość równą dokładnie $n$ . Złożoność ta implikuje, że o ile $P \neq NP$ , nie istnieje algorytm o wielomianowej złożoności czasowej $T(n) = n^k$ , który rozwiązywałby ten problem dla dowolnej instancji wejściowej.

W praktyce algorytmicznej najskuteczniejszym dokładnym podejściem do problemu $\text{HC}$ jest metoda programowania dynamicznego oparta na technice „subset DP”. Najbardziej znanym rozwiązaniem tego typu jest algorytm Helda-Karpa, którego złożoność czasowa wynosi $O(n^2 2^n)$ , a złożoność pamięciowa $O(n 2^n)$ . Algorytm ten wykorzystuje funkcję stanu $f(S, v)$ , reprezentującą informację, czy istnieje ścieżka Hamiltona w podzbiorze wierzchołków $S \subseteq V$ kończąca się w wierzchołku $v$ . Równanie rekurencyjne przyjmuje postać $f(S, v) = \bigvee_{u \in S \setminus {v}, {u, v} \in E} f(S \setminus {v}, u)$ . Choć jest to wynik wykładniczy, stanowi on znaczną poprawę względem naiwnego przeglądu wszystkich permutacji o złożoności $O(n!)$ , co przy zastosowaniu wzoru Stirlinga $n! \approx \sqrt{2\pi n} (\frac{n}{e})^n$ pokazuje gigantyczną różnicę w tempie wzrostu funkcji kosztu.

Badania nad złożonością problemu Hamiltona obejmują również specyficzne klasy grafów, gdzie problem ten może stać się łatwiejszy. Przykładowo, dla grafów o ograniczonym parametrze szerokości drzewiastej (treewidth), oznaczanym jako $tw(G)$ , problem ten można rozwiązać w czasie $O(c^{tw(G)} n)$ , co plasuje go w klasie problemów stałoparametrowo pijalnych (FPT). Z drugiej strony, problem pozostaje NP-zupełny nawet dla bardzo restrykcyjnych klas, takich jak grafy planarne o maksymalnym stopniu wierzchołka $\Delta(G) = 3$ czy grafy kratowe. To pokazuje, że trudność znalezienia cyklu Hamiltona nie wynika z globalnej gęstości krawędzi, lecz z lokalnych ograniczeń strukturalnych, które uniemożliwiają łatwe „sklejanie” lokalnych ścieżek w jeden globalny cykl obejmujący całą przestrzeń wierzchołkową.

3. Twierdzenie Diraca o stopniu wierzchołków

Twierdzenie sformułowane przez Gabriela Diraca w 1952 roku stanowi fundament współczesnej teorii grafów hamiltonowskich, będąc pierwszym szeroko uznanym warunkiem wystarczającym, opartym na minimalnym stopniu wierzchołka grafu. Formalna treść twierdzenia głosi, że jeżeli $G = (V, E)$ jest grafem prostym o liczbie wierzchołków $n \geq 3$ oraz minimalny stopień wierzchołka spełnia nierówność $\delta(G) \geq \frac{n}{2}$ , to graf $G$ posiada cykl Hamiltona. Warunek ten, zapisywany często jako $\forall_{v \in V} d(v) \geq \frac{n}{2}$ , jest w pewnym sensie optymalny, ponieważ dla dowolnego parzystego $n$ można skonstruować graf niehamiltonowski składający się z dwóch rozłącznych grafów pełnych $K_{n/2}$ , gdzie stopnie wierzchołków wynoszą dokładnie $\frac{n}{2} - 1$ , co pokazuje, że nawet niewielkie odstępstwo od tej granicy może uniemożliwić istnienie cyklu.

Dowód twierdzenia Diraca zazwyczaj przeprowadza się metodą nie wprost, zakładając istnienie grafu spełniającego warunek stopnia, który nie jest hamiltonowski. Rozważamy wówczas graf $G$ , który jest maksymalny pod względem liczby krawędzi wśród grafów niehamiltonowskich o rzędzie $n$ spełniających warunek Diraca. Dodanie dowolnej krawędzi ${u, v} \notin E$ do takiego grafu musi utworzyć cykl Hamiltona, co oznacza, że w pierwotnym grafie $G$ musiała istnieć ścieżka Hamiltona $(v_1, v_2, \dots, v_n)$ łącząca $u = v_1$ z $v = v_n$ . Aby uniknąć cyklu Hamiltona, nie może istnieć takie $i \in {2, \dots, n-1}$ , dla którego jednocześnie zachodzą relacje ${v_1, v_i} \in E$ oraz ${v_{i-1}, v_n} \in E$ . Jeśli bowiem taka para krawędzi by istniała, moglibyśmy skonstruować cykl $(v_1, v_i, v_{i+1}, \dots, v_n, v_{i-1}, v_{i-2}, \dots, v_1)$ , co przeczyłoby założeniu o niehamiltonowskości grafu $G$ .

Analiza kombinatoryczna zbiorów sąsiadów wierzchołków krańcowych ścieżki prowadzi do sprzeczności z warunkiem Diraca. Definiujemy dwa zbiory indeksów: $S = {i : {v_1, v_{i+1}} \in E}$ oraz $T = {i : {v_i, v_n} \in E}$ . Zauważamy, że oba te zbiory są podzbiorami ${1, 2, \dots, n-1}$ . Liczność tych zbiorów odpowiada stopniom wierzchołków, czyli $|S| = d(v_1) \geq \frac{n}{2}$ oraz $|T| = d(v_n) \geq \frac{n}{2}$ . Gdyby zbiory $S$ i $T$ były rozłączne, to suma ich liczności musiałaby spełniać $|S| + |T| \leq n-1$ . Jednakże, podstawiając warunki Diraca, otrzymujemy $\frac{n}{2} + \frac{n}{2} \leq n-1$ , co prowadzi do absurdalnej nierówności $n \leq n-1$ . Zatem $S \cap T \neq \emptyset$ , co potwierdza istnienie indeksu $i$ domykającego cykl i kończy dowód poprzez wykazanie, że każdy graf o tak wysokich stopniach wierzchołków musi być hamiltonowski.

Warto podkreślić, że twierdzenie Diraca jest warunkiem bardzo silnym i dotyczy grafów gęstych, w których liczba krawędzi musi wynosić co najmniej $|E| \geq \frac{1}{2} n (\frac{n}{2}) = \frac{n^2}{4}$ . W rzeczywistych zastosowaniach, takich jak sieci telekomunikacyjne czy topologie rozproszone, często szuka się grafów rzadkich posiadających cykl Hamiltona, gdzie $|E|$ jest rzędu $O(n)$ . Twierdzenie to pokazuje jednak istotną zależność: lokalna gęstość połączeń (stopień każdego punktu) przekłada się bezpośrednio na globalną strukturę (istnienie cyklu spinającego). Rozszerzeniem tego podejścia są badania nad grafami losowymi w modelu Erdősa-Rényiego $G(n, p)$ , gdzie prawdopodobieństwo istnienia cyklu Hamiltona dąży do jedności, gdy $p \approx \frac{\ln n + \ln \ln n}{n}$ , co jest wartością znacznie mniejszą niż wymagana przez deterministyczne twierdzenie Diraca.

4. Twierdzenie Orego i uogólnienie warunków brzegowych

Twierdzenie sformułowane przez norweskiego matematyka Oysteina Orego w 1960 roku stanowi istotne wzmocnienie wyniku Diraca, przesuwając punkt ciężkości z minimalnego stopnia pojedynczego wierzchołka na sumaryczną gęstość połączeń między parami wierzchołków nieprzyległych. Formalna teza twierdzenia Orego stwierdza, że jeśli $G = (V, E)$ jest grafem prostym o rzędzie $n \geq 3$ i dla każdej pary wierzchołków $u, v \in V$ , które nie są połączone krawędzią, zachodzi nierówność $d(u) + d(v) \geq n$ , to graf $G$ jest hamiltonowski. Warunek ten jest słabszy niż warunek Diraca, ponieważ dopuszcza istnienie wierzchołków o stopniu mniejszym niż $n/2$ , pod warunkiem, że ich potencjalny brak połączeń jest kompensowany przez odpowiednio wysokie stopnie innych wierzchołków w strukturze grafu.

Mechanizm dowodowy twierdzenia Orego opiera się na podobnej technice sprzeczności, co dowód Diraca, lecz operuje na szerszej klasie par wierzchołków. Zakładając, że istnieje graf spełniający warunek Orego, który nie posiada cyklu Hamiltona, możemy rozważyć graf maksymalny $G^*$ , w którym dodanie dowolnej brakującej krawędzi ${u, v}$ domyka cykl. W takim grafie musi istnieć ścieżka Hamiltona $(v_1, v_2, \dots, v_n)$ , gdzie $u = v_1$ oraz $v = v_n$ . Analizując zbiory sąsiedztwa $N(v_1)$ oraz $N(v_n)$ , definiujemy odpowiednio indeksy $i$ takie, że $v_{i+1}$ jest sąsiadem $v_1$ oraz $v_i$ jest sąsiadem $v_n$ . Z zasady szufladkowej Dirichaleta wynika, że przy sumie stopni $d(v_1) + d(v_n) \geq n$ musi istnieć co najmniej jeden indeks $i$ , dla którego oba te warunki są spełnione jednocześnie, co pozwala na rekonfugurowanie ścieżki w cykl $(v_1, v_{i+1}, v_{i+2}, \dots, v_n, v_i, v_{i-1}, \dots, v_1)$ .

Uogólnienie warunków brzegowych wynikające z twierdzenia Orego prowadzi do wniosku, że hamiltonowskość grafu jest własnością stabilną względem sumy stopni. Jeśli bowiem zdefiniujemy własność $P$ jako istnienie cyklu Hamiltona, to twierdzenie Orego pokazuje, że $P$ jest $n$ -stabilne. Oznacza to, że jeśli $G + {u, v}$ posiada cykl Hamiltona i $d(u) + d(v) \geq n$ , to sam graf $G$ również musiał go posiadać. Ta obserwacja stała się fundamentem pod późniejszą teorię domknięć grafów. Granica $n$ w sumie stopni jest nieprzekraczalna w sensie ogólnym; klasycznym przykładem grafu ekstremalnego, który niemal spełnia warunek Orego, ale nie jest hamiltonowski, jest graf $K_{m, m+1}$ (pełny graf dwudzielny), gdzie dla par wierzchołków z większej partycji suma stopni wynosi $m + m = 2m$ , podczas gdy liczba wierzchołków $n = 2m + 1$ .

W kontekście uogólnień, warto wspomnieć o warunku Chvátala-Erdősa, który wiąże hamiltonowskość z parametrem spójności wierzchołkowej $\kappa(G)$ oraz liczbą stabilności $\alpha(G)$ , oznaczającą maksymalną liczność zbioru niezależnego. Twierdzenie to mówi, że jeśli $\kappa(G) \geq \alpha(G)$ , to graf posiada cykl Hamiltona (wyłączając graf $K_2$ ). Jest to głębokie uogólnienie, gdyż warunki typu stopnia (jak u Diraca czy Orego) w istocie wymuszają odpowiednio wysoką spójność w stosunku do wielkości zbiorów niezależnych. W ten sposób teoria Hamiltona przechodzi od prostych statystyk stopni wierzchołków ku zaawansowanym niezmiennikom strukturalnym, które lepiej opisują topologię sieci o nieregularnym rozkładzie krawędzi.

5. Domknięcie grafu Bondy-Chvátala

Koncepcja domknięcia grafu, wprowadzona przez Adriana Bondy’ego i Václava Chvátala w 1976 roku, stanowi jedno z najpotężniejszych narzędzi w teorii grafów hamiltonowskich, formalizując obserwacje poczynione wcześniej przez Orego. Domknięcie grafu $G = (V, E)$ o rzędzie $n$ , oznaczane symbolem $cl(G)$ , definiuje się jako graf powstały z $G$ poprzez sukcesywne dodawanie krawędzi ${u, v}$ między każdą parą niepołączonych wierzchołków $u, v \in V$ , których suma stopni spełnia nierówność $d(u) + d(v) \geq n$ . Proces ten jest powtarzany iteracyjnie: po dodaniu nowej krawędzi stopnie wierzchołków $u$ oraz $v$ zwiększają się, co może sprawić, że inne pary wierzchołków zaczną spełniać warunek sumy stopni, umożliwiając dalszą rozbudowę struktury, aż do momentu, gdy żadna nowa krawędź nie może zostać dodana.

Fundamentem tej teorii jest twierdzenie o stabilności hamiltonowskości, które głosi, że graf $G$ jest hamiltonowski wtedy i tylko wtedy, gdy jego domknięcie $cl(G)$ jest hamiltonowskie. Matematycznie zapisujemy to jako równoważność $G \in \mathcal{H} \iff cl(G) \in \mathcal{H}$ , gdzie $\mathcal{H}$ jest zbiorem grafów posiadających cykl Hamiltona. Dowód tego twierdzenia opiera się na fakcie, że jeśli $d(u) + d(v) \geq n$ , to dodanie krawędzi ${u, v}$ nie tworzy cyklu Hamiltona „z niczego” – jeśli cykl taki istnieje w $G + {u, v}$ , to musiał istnieć już w $G$ , co wynika bezpośrednio z lematu wykorzystanego w dowodzie twierdzenia Orego. Dzięki temu, zamiast analizować skomplikowaną strukturę rzadkiego grafu $G$ , możemy badać jego znacznie gęstsze domknięcie.

Niezwykle istotną własnością domknięcia $cl(G)$ jest jego jednoznaczność. Bez względu na kolejność, w jakiej wybieramy pary wierzchołków $u, v$ do połączenia, końcowy nadgraf zawsze będzie identyczny. Operację tę można opisać jako proces osiągania punktu stałego przekształcenia $\Psi(G)$ , gdzie $\Psi$ dodaje wszystkie możliwe krawędzie spełniające warunek $d(u) + d(v) \geq n$ . Jeśli w wyniku tego procesu otrzymamy graf pełny $K_n$ , wówczas mamy absolutną pewność, że wyjściowy graf $G$ posiada cykl Hamiltona. Jest to bardzo silne kryterium, ponieważ wiele grafów, które nie spełniają bezpośrednio warunku Diraca czy Orego, posiada domknięcie będące grafem pełnym, co pozwala na ich szybką klasyfikację jako grafów hamiltonowskich.

Złożoność algorytmiczna wyznaczania domknięcia $cl(G)$ jest relatywnie niska i wynosi $O(n^4)$ w wersji naiwnej lub $O(n^3)$ przy zastosowaniu odpowiednich kolejek wierzchołków, co jest wynikiem wielomianowym i wysoce efektywnym w porównaniu do problemu NP-zupełnego poszukiwania samego cyklu. Warto jednak zaznaczyć, że chociaż $cl(G) = K_n$ jest warunkiem wystarczającym, nie jest on warunkiem koniecznym – istnieją grafy hamiltonowskie, których domknięcie nie jest grafem pełnym, a nawet takie, w których $cl(G) = G$ . Przykładem może być cykl $C_n$ dla $n \geq 5$ , gdzie stopień każdego wierzchołka wynosi $2$ , więc suma stopni dowolnej pary to $4 < n$ , co oznacza, że domknięcie nie doda żadnej krawędzi, mimo że graf z definicji jest hamiltonowski.

6. Grafy turniejowe i ich specyfika

Grafy turniejowe stanowią szczególną klasę grafów skierowanych (digrafów), które powstają poprzez nadanie kierunku każdej krawędzi w grafie pełnym $K_n$ . Formalnie, turniej $T = (V, A)$ to graf skierowany, w którym dla każdej pary rozłącznych wierzchołków $u, v \in V$ zbiór łuków $A$ zawiera dokładnie jeden z łuków: albo $(u, v) \in A$ , albo $(v, u) \in A$ . Taka struktura matematycznie modeluje wyniki zawodów sportowych systemem „każdy z każdym”, gdzie nie występują remisy. Relacja ta jest asymetryczna i kompletna, co nadaje turniejom unikalne własności w kontekście ścieżek i cykli Hamiltona, znacząco odbiegające od ogólnych grafów skierowanych, w których problem ten pozostaje NP-zupełny.

Jednym z fundamentalnych wyników w tej dziedzinie jest twierdzenie Redei’ego z 1934 roku, które głosi, że każdy turniej posiada przynajmniej jedną ścieżkę Hamiltona. Dowód tego twierdzenia zazwyczaj przeprowadza się metodą indukcji po liczbie wierzchołków $n$ . Dla $n=1$ teza jest trywialna. Zakładając, że turniej o $k$ wierzchołkach posiada ścieżkę $P = (v_1, v_2, \dots, v_k)$ , rozważamy nowy wierzchołek $u$ . Jeśli istnieje łuk $(u, v_1)$ , nową ścieżką jest $(u, v_1, \dots, v_k)$ . Jeśli nie, a istnieje łuk $(v_k, u)$ , ścieżką jest $(v_1, \dots, v_k, u)$ . W przeciwnym razie musi istnieć taki indeks $i$ , że $(v_i, u) \in A$ oraz $(u, v_{i+1}) \in A$ , co pozwala na wstawienie $u$ wewnątrz ścieżki, tworząc ciąg $(v_1, \dots, v_i, u, v_{i+1}, \dots, v_k)$ .

Kwestia istnienia cyklu Hamiltona w turnieju jest ściśle powiązana z pojęciem silnej spójności. Turniej $T$ jest silnie spójny, jeśli dla każdej pary wierzchołków $u, v \in V$ istnieje ścieżka skierowana od $u$ do $v$ . Twierdzenie Camiona z 1959 roku stanowi, że turniej $T$ posiada cykl Hamiltona wtedy i tylko wtedy, gdy jest on silnie spójny. To kryterium jest niezwykle eleganckie, ponieważ silną spójność można zweryfikować w czasie liniowym $O(n + m)$ , gdzie $m$ to liczba łuków, za pomocą algorytmu Tarjana lub Kosaraju. W kontekście turniejów, gdzie $m = \frac{n(n-1)}{2}$ , sprawdzenie hamiltonowskości staje się zadaniem o złożoności wielomianowej $O(n^2)$ .

Dodatkowo, turnieje wykazują własność pancykliczności. Twierdzenie Harary’ego i Mosera mówi, że jeśli turniej $T$ o rzędzie $n$ jest silnie spójny, to dla każdego $k \in {3, 4, \dots, n}$ turniej ten zawiera cykl o długości dokładnie $k$ . Oznacza to, że silna spójność w turnieju nie tylko gwarantuje cykl Hamiltona (który jest cyklem o długości $n$ ), ale wymusza istnienie całej hierarchii cykli o wszystkich możliwych długościach. Własność ta wynika z faktu, że w silnie spójnym turnieju każdy cykl długości $k < n$ może zostać „rozszerzony” do cyklu długości $k+1$ poprzez wykorzystanie wierzchołków zewnętrznych, co pokazuje niesamowitą gęstość strukturalną tych grafów.

Warto również wspomnieć o rozkładzie partytatywnym i wynikach Landaua dotyczących ciągów wyników (score sequences). Ciąg $(s_1, s_2, \dots, s_n)$ , gdzie $s_i$ jest stopniem wyjściowym $d^+(v_i)$ wierzchołka $v_i$ , determinuje wiele własności turnieju. Zgodnie z twierdzeniem Landaua, ciąg liczb nieujemnych w porządku niemalejącym jest ciągiem wyników pewnego turnieju wtedy i tylko wtedy, gdy dla każdego $k \in {1, \dots, n-1}$ zachodzi $\sum_{i=1}^k s_i \geq \frac{k(k-1)}{2}$ , przy czym dla $k=n$ zachodzi równość. Turniej jest silnie spójny (a zatem hamiltonowski) wtedy i tylko wtedy, gdy dla każdego $k < n$ suma ta jest ostro większa niż $\frac{k(k-1)}{2}$ .

7. Algorytm Robertsa-Floresa i poszukiwanie z nawrotami

Algorytm Robertsa-Floresa stanowi klasyczne podejście do problemu wyznaczania cykli Hamiltona w grafach o dowolnej strukturze, wykorzystując technikę przeszukiwania z nawrotami (backtracking). Metoda ta operuje na strukturze drzewa poszukiwań, gdzie każdy węzeł reprezentuje częściową ścieżkę prostą $P = (v_1, v_2, \dots, v_k)$ , a krawędzie drzewa odpowiadają rozszerzeniom tej ścieżki o kolejny wierzchołek $v_{k+1}$ taki, że ${v_k, v_{k+1}} \in E$ . Algorytm dąży do znalezienia permutacji $\sigma$ zbioru wierzchołków, która spełnia warunek sąsiedztwa dla wszystkich par $(v_{\sigma(i)}, v_{\sigma(i+1)})$ oraz dla pary zamykającej $(v_{\sigma(n)}, v_{\sigma(1)})$ . W przeciwieństwie do metod heurystycznych, algorytm ten gwarantuje znalezienie wszystkich cykli Hamiltona lub udowodnienie ich braku, choć odbywa się to kosztem wysokiej złożoności czasowej.

Proces poszukiwania rozpoczyna się od ustalenia arbitralnego wierzchołka startowego $v_1$ , co jest dopuszczalne, gdyż cykl Hamiltona musi przechodzić przez każdy wierzchołek grafu. W każdym kroku algorytm utrzymuje zbiór wierzchołków już odwiedzonych $V_{visited} = {v_1, \dots, v_k}$ oraz stos wierzchołków tworzących aktualną ścieżkę. Dla aktualnego wierzchołka $v_k$ przeszukiwana jest lista sąsiedztwa $N(v_k)$ w celu znalezienia kandydata $u \in N(v_k)$ , który nie należy do $V_{visited}$ . Jeśli taki wierzchołek istnieje, zostaje on dołączony do ścieżki jako $v_{k+1}$ , a algorytm przechodzi do kroku $k+1$ . Jeśli natomiast zbiór dostępnych sąsiadów $N(v_k) \setminus V_{visited}$ jest pusty, algorytm wykonuje nawrót (backtrack), usuwając $v_k$ ze ścieżki i próbując alternatywnego sąsiada dla wierzchołka $v_{k-1}$ .

Formalna warunek zakończenia sukcesem następuje w momencie, gdy długość ścieżki osiągnie wartość $k = n = |V|$ . Wówczas algorytm musi jedynie sprawdzić, czy ostatni wierzchołek $v_n$ jest połączony krawędzią z wierzchołkiem startowym $v_1$ , czyli czy zachodzi relacja ${v_n, v_1} \in E$ . Jeśli tak, zbiór krawędzi $E_{H} = {{v_1, v_2}, {v_2, v_3}, \dots, {v_n, v_1}}$ tworzy cykl Hamiltona. Złożoność obliczeniowa tego podejścia w najgorszym przypadku jest rzędu $O(n!)$ , co wynika z liczby możliwych permutacji wierzchołków, jednak w praktyce wydajność algorytmu Robertsa-Floresa jest znacznie lepsza dzięki zastosowaniu technik ucinania gałęzi (pruning), takich jak sprawdzanie stopnia wierzchołków w pozostałym podgrafie indukowanym $G[V \setminus V_{visited}]$ .

Istotnym usprawnieniem algorytmu jest monitorowanie spójności grafu w trakcie budowania ścieżki. Jeśli w dowolnym kroku $k < n$ usunięcie wierzchołków ze zbioru $V_{visited}$ powoduje, że graf $G - V_{visited}$ staje się niespójny lub liczba jego składowych spójnych przekracza dopuszczalne limity dla grafu hamiltonowskiego, można natychmiast przerwać przeszukiwanie danej gałęzi. Inna optymalizacja opiera się na obserwacji stopni wierzchołków: jeśli jakikolwiek nieodwiedzony jeszcze wierzchołek $u \notin V_{visited}$ posiada w grafie indukowanym mniej niż $2$ dostępnych krawędzi (włączając połączenie z aktualnym końcem ścieżki $v_k$ oraz wierzchołkiem startowym $v_1$ ), to ścieżka ta nigdy nie zostanie domknięta do cyklu Hamiltona. Te reguły pozwalają zredukować przestrzeń poszukiwań $S \subseteq \text{Sym}(V)$ do znacznie mniejszego, choć nadal potencjalnie dużego zbioru.

8. Warunki konieczne i cięcia w grafie

Istnienie cyklu Hamiltona nakłada na strukturę grafu surowe restrykcje, które muszą być spełnione, aby dany graf mógł być uznany za hamiltonowski. Najważniejszym warunkiem koniecznym, wynikającym bezpośrednio z topologii cyklu, jest relacja między liczbą usuwanych wierzchołków a liczbą powstałych składowych spójnych. Jeśli graf $G = (V, E)$ jest hamiltonowski, to dla każdego niepustego właściwego podzbioru wierzchołków $S \subset V$ musi zachodzić nierówność $\omega(G - S) \leq |S|$ , gdzie $\omega(G - S)$ oznacza liczbę składowych spójnych grafu powstałego po usunięciu zbioru $S$ . Intuicyjnie, każdy cykl Hamiltona musi „wejść” do każdej składowej i „wyjść” z niej, co wymaga co najmniej tylu wierzchołków pośredniczących w zbiorze $S$ , ile jest odizolowanych części grafu. Jeśli znajdziemy zbiór $S$ , dla którego $\omega(G - S) > |S|$ , jest to ostateczny dowód na brak cyklu Hamiltona.

Kolejnym istotnym warunkiem koniecznym jest spójność wierzchołkowa grafu. Każdy graf hamiltonowski $G$ musi być co najmniej 2-spójny, co formalnie zapisujemy jako $\kappa(G) \geq 2$ . Oznacza to, że usunięcie dowolnego pojedynczego wierzchołka $v \in V$ nie może rozspójnić grafu. Wynika to z faktu, że cykl Hamiltona dostarcza dwóch rozłącznych ścieżek wierzchołkowych między dowolną parą węzłów $u, w \in V$ . W grafach, które posiadają wierzchołki rozdzielające (artykulacyjne), czyli takie, że $\omega(G - {v}) > 1$ , niemożliwe jest skonstruowanie cyklu przechodzącego przez wszystkie punkty bez dwukrotnego odwiedzenia wierzchołka $v$ , co wprost łamie definicję drogi Hamiltona. Własność ta jest często wykorzystywana do szybkiej eliminacji kandydatów na grafy hamiltonowskie w algorytmach optymalizacyjnych.

Analiza cięć krawędziowych również dostarcza cennych informacji o potencjalnej hamiltonowskości. W grafie hamiltonowskim, dla każdego cięcia $(S, V \setminus S)$ , liczba krawędzi przechodzących przez to cięcie, oznaczana jako $|[S, V \setminus S]|$ , musi być liczbą parzystą i wynosić co najmniej $2$ . Jest to warunek trywialny dla spójności, ale w przypadku cyklu Hamiltona każda składowa indukowana przez zbiór $S$ musi zostać połączona z resztą grafu parzystą liczbą krawędzi należących do cyklu (wejście i wyjście). Jeśli w grafie o parzystej liczbie wierzchołków istnieje cięcie krawędziowe o rozmiarze $1$ (most), graf ten natychmiast uznaje się za niehamiltonowski. Ponadto, jeśli stopień dowolnego wierzchołka wynosi dokładnie $d(v) = 2$ , to obie krawędzie incydentne z tym wierzchołkiem muszą obligatoryjnie należeć do każdego potencjalnego cyklu Hamiltona.

Warto również wspomnieć o pojęciu grafów dwudzielnych w kontekście warunków koniecznych. Dla grafu dwudzielnego $G = (V_1 \cup V_2, E)$ , gdzie $V_1$ i $V_2$ są zbiorami niezależnymi, cykl Hamiltona może istnieć tylko wtedy, gdy liczności obu zbiorów są równe, czyli $|V_1| = |V_2|$ . Wynika to z faktu, że cykl w grafie dwudzielnym musi naprzemiennie odwiedzać wierzchołki z obu partycji. Jeśli $||V_1| - |V_2|| > 0$ , graf nie posiada cyklu Hamiltona, a jeśli $||V_1| - |V_2|| > 1$ , graf nie posiada nawet ścieżki Hamiltona. To proste arytmetyczne kryterium pozwala na natychmiastową ocenę wielu struktur kratowych i siatkowych, które często pojawiają się w problemach logistycznych i projektowaniu układów scalonych.

9. Grafy planarne i twierdzenie Tutte’a

Grafy planarne, czyli takie, które można narysować na płaszczyźnie bez przecinania się krawędzi, wykazują unikalne właściwości w odniesieniu do cykli Hamiltona. Historycznie problem ten był silnie motywowany próbami udowodnienia twierdzenia o czterech barwach, gdzie Peter Tait wysunął błędną hipotezę, że każdy graf planarny 3-regularny i 3-spójny (wielościenny) jest hamiltonowski. Hipoteza ta, gdyby była prawdziwa, uprościłaby dowód kolorowania map, jednak została obalona przez Williama Tutte’a, który w 1946 roku skonstruował kontrprzykład znany jako graf Tutte’a. Graf ten posiada $n = 46$ wierzchołków i $69$ krawędzi, a jego struktura uniemożliwia istnienie cyklu przechodzącego przez wszystkie punkty, mimo spełnienia rygorystycznych warunków spójności.

Przełomem w badaniach nad planarnością było twierdzenie Tutte’a z 1956 roku, które podaje warunek wystarczający dla istnienia cyklu Hamiltona. Głosi ono, że każdy graf planarny 4-spójny wierzchołkowo posiada cykl Hamiltona. Formalnie, jeśli dla grafu planarnego $G$ zachodzi $\kappa(G) \geq 4$ , to $G$ jest hamiltonowski. Jest to wynik o ogromnym znaczeniu, ponieważ spójność na poziomie $4$ gwarantuje wystarczającą gęstość połączeń wewnętrznych, aby uniknąć lokalnych pułapek strukturalnych, które występują w grafach 3-spójnych. Dowód tego twierdzenia jest niezwykle złożony i opiera się na teorii mostów Tutte’a względem cyklu oraz indukcji po liczbie ścian grafu $f$ , gdzie zgodnie ze wzorem Eulera zachodzi relacja $n - m + f = 2$ .

W kontekście grafów planarnych istotne jest również pojęcie grafów dualnych. Jeśli graf planarny $G$ jest hamiltonowski, to jego graf dualny $G^*$ musi posiadać specyficzny podział ścian. Krawędzie cyklu Hamiltona w $G$ wyznaczają zbiór krawędzi w $G^*$ , które tworzą drzewo rozpinające, co jest związane z własnością, że cykl Hamiltona dzieli płaszczyznę na dwa obszary (wewnętrzny i zewnętrzny) zgodnie z twierdzeniem Jordana o krzywej zamkniętej. Liczba ścian wewnątrz cyklu $f_{in}$ oraz na zewnątrz $f_{out}$ musi spełniać równanie $\sum (i-2) c_i = n-2$ , gdzie $c_i$ oznacza liczbę ścian będących $i$ -kątami. Te kombinatoryczne zależności pozwalają na stosowanie metod programowania liniowego do wykluczania hamiltonowskości w złożonych sieciach planarnych.

Dalsze badania nad grafami planarnymi doprowadziły do sformułowania twierdzenia o grafach halinowskich. Graf Halina to graf planarny utworzony przez drzewo $T$ , które nie ma wierzchołków stopnia $2$ , poprzez połączenie wszystkich jego liści cyklem w porządku wyznaczonym przez zanurzenie planarne. Każdy graf Halina jest hamiltonowski, co więcej, posiada on własność niemal pancykliczności. Warto zauważyć, że podczas gdy dla ogólnych grafów problem Hamiltona jest $NP$ -zupełny, to dla niektórych podklas grafów planarnych o ograniczonym stopniu wierzchołków lub specyficznej strukturze ścian istnieją algorytmy o niższej złożoności, choć dla ogólnej klasy grafów planarnych o maksymalnym stopniu $\Delta(G) = 3$ problem pozostaje trudny obliczeniowo.

10. Hipoteza Chvátala i grafy twarde

Pojęcie twardości grafu, wprowadzone przez Václava Chvátala w 1973 roku, stanowi próbę liczbowego ujęcia globalnej spójności grafu w relacji do jego podatności na rozbicie na składowe spójne. Twardość grafu $G = (V, E)$ , oznaczaną symbolem $\tau(G)$ , definiuje się jako $\tau(G) = \min \frac{|S|}{\omega(G-S)}$ , gdzie minimum jest brane po wszystkich takich podzbiorach wierzchołków $S \subset V$ , których usunięcie rozspójnia graf, czyli $\omega(G-S) > 1$ . W przypadku grafów pełnych $K_n$ przyjmuje się umownie $\tau(K_n) = \frac{n-1}{1}$ . Intuicyjnie, parametr ten określa, jak „trudno” jest rozbić graf na wiele izolowanych części przy użyciu relatywnie małej liczby wierzchołków. Chvátal zauważył, że istnieje głęboka korelacja między wysoką wartością $\tau(G)$ a istnieniem cykli Hamiltona.

Bezpośrednim wnioskiem z warunku koniecznego hamiltonowskości, który mówi, że dla każdego $S$ zachodzi $\omega(G-S) \leq |S|$ , jest stwierdzenie, że każdy graf hamiltonowski musi być co najmniej 1-twardy, czyli $\tau(G) \geq 1$ . Chvátal postawił jednak znacznie śmielszą hipotezę, sugerując istnienie stałej $t_0$ takiej, że każdy graf o twardości $\tau(G) \geq t_0$ jest hamiltonowski. Pierwotnie przypuszczano, że stała ta może wynosić $t_0 = 2$ , co oznaczałoby, że każdy graf 2-twardy posiada cykl Hamiltona. Hipoteza ta, znana jako hipoteza o 2-twardości, przez dekady stymulowała rozwój ekstremalnej teorii grafów i poszukiwania struktur o wysokiej spójności, które mimo to pozostają niehamiltonowskie.

Dalsze badania doprowadziły do obalenia hipotezy dla wartości $t_0 = 2$ . Bauer, Broersma i Veldman skonstruowali w 2000 roku rodziny grafów, które są dowolnie bliskie twardości $9/4$ , a mimo to nie zawierają cyklu Hamiltona. Wykazano, że dla dowolnego $\epsilon > 0$ istnieją grafy o twardości $\tau(G) = \frac{9}{4} - \epsilon$ , które nie są hamiltonowskie. Obecnie wiadomo, że jeśli taka stała $t_0$ istnieje, musi ona spełniać nierówność $t_0 \geq \frac{9}{4}$ . Mimo braku ogólnego dowodu dla wszystkich grafów, hipoteza Chvátala została potwierdzona dla wielu klas specjalnych, takich jak grafy planarne czy grafy o ograniczonym stopniu wierzchołków, co czyni twardość jednym z najbardziej precyzyjnych narzędzi opisu strukturalnego w problemach cyklu Hamiltona.

Zastosowanie parametru $\tau(G)$ wykracza poza czystą teorię grafów, znajdując odzwierciedlenie w analizie niezawodności sieci. Wysoka twardość oznacza, że sieć jest odporna na kaskadowe awarie węzłów, które mogłyby doprowadzić do jej fragmentacji. Matematyczna relacja $\tau(G) \leq \frac{\kappa(G)}{\alpha(G)}$ , wiążąca twardość ze spójnością wierzchołkową $\kappa(G)$ i liczbą stabilności $\alpha(G)$ , pokazuje, że grafy o małych zbiorach niezależnych i wysokiej spójności naturalnie dążą do bycia hamiltonowskimi. Problem obliczania dokładnej wartości $\tau(G)$ dla danego grafu jest sam w sobie problemem $NP$ -trudnym, co dodatkowo podkreśla głębię i złożoność powiązań między twardością a cyklem Hamiltona.

11. Podsumowanie

Synteza współczesnej wiedzy o cyklu Hamiltona prowadzi do wniosku, że jest to jedno z najgłębiej spenetrowanych, a zarazem wciąż zagadkowych zagadnień kombinatoryki ekstremalnej i algorytmicznej. Z matematycznego punktu widzenia, istnienie cyklu Hamiltona w grafie $G = (V, E)$ jest przejawem wysokiej spójności strukturalnej, która pozwala na uformowanie podgrafu izomorficznego z $C_n$ . Rozważania te rozpoczęły się od prostych warunków lokalnych, takich jak twierdzenie Diraca wymagające $d(v) \geq n/2$ , co implikuje minimalną liczbę krawędzi $|E| \geq n^2/4$ , a ewoluowały w stronę globalnych niezmienników, takich jak domknięcie grafu $cl(G)$ czy parametr twardości $\tau(G)$ . Kluczowym osiągnięciem teoretycznym jest zrozumienie, że hamiltonowskość jest własnością monotoniczną – dodanie krawędzi do grafu hamiltonowskiego nigdy nie niszczy tej własności, co pozwala na badanie jej przez pryzmat rodzin grafów o narastającej gęstości.

Z perspektywy teorii złożoności obliczeniowej, problem $\text{HC} \in \text{NPC}$ stanowi barierę, której nie udało się przełamać za pomocą algorytmów wielomianowych, co zmusza badaczy do poszukiwania rozwiązań w ramach paradygmatu algorytmów wykładniczych o zredukowanej podstawie, takich jak $O(1.657^n)$ przy użyciu metod algebraicznych i inkluzji-ekskluzji. Różnica między cyklem Eulera, rozstrzygalnym w czasie $O(m)$ , a cyklem Hamiltona, ilustruje fundamentalny podział w informatyce teoretycznej między problemami klasy $P$ a $NP$ . Jednocześnie, rozwój metod probabilistycznych pokazał, że dla grafów losowych $G(n, p)$ granica hamiltonowskości pokrywa się z granicą minimalnego stopnia $\delta(G) \geq 2$ , co zachodzi, gdy $p = \frac{\ln n + \ln \ln n + c}{n}$ , rzucając nowe światło na rzadkie struktury posiadające tę własność.

Współczesne opracowania kładą duży nacisk na zastosowania praktyczne, gdzie cykl Hamiltona służy jako model optymalizacyjny w logistyce, genomice przy asemblacji sekwencji DNA, oraz w projektowaniu systemów odpornych na błędy. Relacja $\omega(G - S) \leq |S|$ pozostaje najsilniejszym narzędziem dowodzenia niehamiltonowskości, podczas gdy twierdzenia typu Bondy’ego-Chvátala pozwalają na uproszczenie skomplikowanych sieci do ich postaci pełnych bez utraty informacji o istnieniu cyklu. Całość teorii stanowi spójny gmach matematyczny, w którym prosta definicja ścieżki przechodzącej przez wszystkie punkty $V$ generuje nieskończony ciąg pytań o granice spójności, symetrii i wydajności obliczeniowej, czyniąc grafy hamiltonowskie jednym z najważniejszych tematów badawczych XXI wieku.

13. Bibliografia

R. Diestel, Graph Theory.
D. B. West, Introduction to Graph Theory.
J. A. Bondy, U. S. R. Murty, Graph Theory.
F. Harary, Graph Theory.
B. Bollobás, Modern Graph Theory.
R. J. Wilson, Introduction to Graph Theory.
T. H. Cormen et al., Introduction to Algorithms.
M. Jungnickel, Graphs, Networks and Algorithms.
J. Bang-Jensen, G. Gutin, Digraphs.
S. Even, Graph Algorithms.
R. K. Ahuja et al., Network Flows.

OtagowanoAlgorytm Robertsa-Floresa, cięcia, cykl, cykl Hamiltona, domknięcie, domknięcie grafu, grafy planarne, grafy turniejowe, grafy twarde, heurestyki, Hipoteza Chvátala, poszukiwanie z nawrotami, problem decyzyjny, ścieżka, spójność, stopień wierzchołków, twierdzenie diraca, twierdzenie Ore’a, twierdzenie Tutte'a, warunki brzegowe, złożoność obliczeniowa, łuk

13. Bibliografia

Dodaj komentarz Anuluj pisanie odpowiedzi