Tekst źródłowy strony Ścieżka Hamiltona

[[Plik:Herschel Hamiltonian path.svg|alt=Graf o pięciu wierzchołkach z zaznaczoną ścieżką Hamiltona.|mały|Graf półhamiltonowski z wyróżnioną na niebiesko ścieżką Hamiltona.]]
[[Plik:Hamiltonian.png|alt=Graf o sześciu wierzchołkach z zaznaczonym cyklem Hamiltona.|mały|Graf hamiltonowski z wyróżnionym na czerwono cyklem Hamiltona.]]
'''Ścieżka Hamiltona''' – w [[Teoria grafów|teorii grafów]], [[Ścieżka (teoria grafów)|ścieżka]], która przechodzi przez każdy [[Wierzchołek (teoria grafów)|wierzchołek]] [[Graf (matematyka)|grafu]] dokładnie raz. [[Cykl (teoria grafów)|Ścieżkę zamkniętą]] o tej własności nazywa się '''cyklem Hamiltona''', a graf ją zawierający – '''grafem hamiltonowskim'''<ref name=":0">{{Cytuj |autor = Robin Wilson |tytuł = Wprowadzenie do teorii grafów |data = 2012 |isbn = 9788301150662 |wydawca = Wydawnictwo Naukowe PWN |s = 53-56 |język = pl}}</ref><ref name=":1">{{Cytuj |autor = Reinhard Diestel |tytuł = Graph Theory |data = 2017 |isbn = 9783662536216 |miejsce = Berlin |wydawca = Springer |s = 307–322 |język = en}}</ref><ref name=":2">{{Cytuj |autor = Kenneth Ross; Charles Wright |tytuł = Matematyka dyskretna |data = 2012 |isbn = 9788301143800 |wydawca = Wydawnictwo Naukowe PWN |s = 372-379 |język = pl}}</ref>. Graf niehamiltonowski, ale posiadający ścieżkę Hamiltona nazywa się czasem '''półhamiltonowskim'''<ref name=":0" />.

W przeciwieństwie do [[Graf eulerowski|grafów eulerowskich]], nie jest znana (i prawdopodobnie nie istnieje<ref name=":1" />) prosta charakteryzacja tych grafów, które zawierają cykl Hamiltona<ref name=":1" /><ref name=":2" />. Problem rozstrzygnięcia, czy graf jest hamiltonowski nie ma znanego [[Złożoność obliczeniowa|efektywnego]] [[Algorytm|algorytmu]] rozwiązywania, co więcej jest to [[problem NP-zupełny]]<ref name=":3">{{encyklopedia PWN |id = 3909792 |tytuł = graf Hamiltona |data dostępu = 2024-04-21}}</ref><ref name=":2" /><ref>{{Cytuj |autor = Michael Garey; David Johnson |tytuł = Computers and Intractability: A Guide to the Theory of NP-Completeness |data = 1979 |isbn = 9780716710455 |miejsce = New York |wydawca = Freeman |s = 60 |język = en}}</ref>.

Wymienione tu pojęcia noszą nazwisko [[William Rowan Hamilton|Williama Hamiltona]], który zaproponował grę polegającą na znalezieniu cyklu wzdłuż krawędzi [[Dwunastościan foremny|dwunastościanu foremnego]]<ref name=":0" /><ref name=":3" />. Problem cykli Hamiltona w [[Graf platoński|grafach wielościanów]] był jednak badany już rok wcześniej przez {{Link-interwiki|Thomas Kirkman|Q=Q943561|tekst=Thomasa Kirkmana}}, który podał między innymi przykład wielościanu bez cykli Hamiltona<ref>{{Cytuj |autor = N. L. Biggs |tytuł = T. P. Kirkman, Mathematician |czasopismo = Bulletin of the London Mathematical Society |data = 1981-03 |data dostępu = 2024-04-21 |wolumin = 13 |numer = 2 |s = 97–120 |doi = 10.1112/blms/13.2.97 |url = http://doi.wiley.com/10.1112/blms/13.2.97 |język = en}}</ref>. Ze znajdowaniem ścieżek i cykli Hamiltona związany jest także [[problem skoczka szachowego]] badany już w IX wieku. Obchodami skoczka interesowali się również w XVIII-wieczni matematycy: [[Abraham de Moivre]] oraz [[Leonhard Euler]]<ref>{{Cytuj |autor = John Watkins |tytuł = Across the board: the mathematics of chessboard problems |data = 2004 |isbn = 9780691154985 |wydawca = Princeton University Press |s = 25-38 |język = en}}</ref>.<gallery mode="packed" widths="150" heights="150">
Plik:Hamiltonian path 3d.svg|alt=Cykl Hamiltona zaznaczony na bryle dwunastościanu foremnego.|Dwunastościan foremny z zaznaczonym przykładowym rozwiązaniem gry Hamiltona.
Plik:Hamiltonian path.svg|alt=Cykl Hamiltona zaznaczony na płaskim grafie dwunastościanu foremnego.|Ten sam cykl zaznaczony w [[Graf planarny|grafie płaskim]] dwunastościanu foremnego.
</gallery>

== Przykłady ==
Z reguły przyjmuje się, że <math>K_1</math> – graf o jednym wierzchołku jest hamiltonowski. Liczba grafów hamiltonowskich o <math>n=1,2,3\dots</math> wierzchołkach jest równa odpowiednio<ref name=":4">{{Cytuj |autor = Eric W. Weisstein |tytuł = Hamiltonian Graph |data dostępu = 2024-04-28 |opublikowany = Wolfram MathWorld |url = https://mathworld.wolfram.com/HamiltonianGraph.html |język = en |dostęp = o}}</ref>:
: 1, 0, 1, 3, 8, 48, 383, … {{OEIS|id=A003216}}.
Niektóre [[Klasa grafów|klasy grafów]] mają tę własność, że wszystkie należące do nich grafy są hamiltonowskie<ref name=":4" />:

* [[graf pełny]] <math>K_n</math> o co najmniej trzech wierzchołkach,
* [[pełny graf dwudzielny]] <math>K_{n,n}</math> o co najmniej czterech wierzchołkach,
* <math>n</math>-[[Kostka (teoria grafów)|kostka]] <math>Q_n</math> dla <math>n \ge 2,</math>
* [[Koło (teoria grafów)|koło]] <math>W_n</math> dla <math>n \ge 4,</math>
* [[Graf platoński|grafy platońskie]] ([[Wielościan foremny|wielościanów foremnych]])<ref name=":5">{{Cytuj |autor = Martin Gardner |tytuł = Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi. |czasopismo = Scientific American |data = 1957-05 |data dostępu = 2024-04-28 |issn = 0036-8733 |wolumin = 196 |numer = 5 |s = 150–157 |doi = 10.1038/scientificamerican0557-150 |język = en |dostęp = z}}</ref>,
* grafy [[Wielościan półforemny|wielościanów półforemnych]]<ref name=":5" />.

Każdy graf wielościanu o co najwyżej 10 wierzchołkach jest hamiltonowski. Istnieją 74 niehamiltonowskie grafy wielościanów o 11 wierzchołkach. Spośród nich najmniej krawędzi ma [[graf Herschela]]<ref>{{Cytuj |autor = Eric W. Weisstein |tytuł = Herschel Graph |data dostępu = 2024-04-28 |opublikowany = Wolfram MathWorld |url = https://mathworld.wolfram.com/HerschelGraph.html |język = en |dostęp = o}}</ref>.
{{Grafika rozwinięta
| opis       = Graf Herschela oraz odpowiadający mu wielościan.
| położenie  = center
| grafika1   = Herschel graph no col.svg
| alt1       = Rysunek grafu Herschela na płaszczyźnie
| grafika2   = Herschel enneahedron animated.gif
| alt2       = Animowany wielościan Herschela
}}

== Zobacz też ==
* [[cykl Eulera]]
* [[problem komiwojażera]]

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
{{MathWorld|autor=Eric W. Weisstein|adres=HamiltonianCycle|tytuł=Hamiltonian Cycle|data dostępu=2024-04-28}}{{Kontrola autorytatywna}}

[[Kategoria:Teoria grafów]]
[[Kategoria:William Rowan Hamilton]]