Ścieżka Hamiltona
![Graf o pięciu wierzchołkach z zaznaczoną ścieżką Hamiltona.](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Herschel_Hamiltonian_path.svg/220px-Herschel_Hamiltonian_path.svg.png)
![Graf o sześciu wierzchołkach z zaznaczonym cyklem Hamiltona.](http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Hamiltonian.png/220px-Hamiltonian.png)
Ścieżka Hamiltona – w teorii grafów, ścieżka, która przechodzi przez każdy wierzchołek grafu dokładnie raz. Ścieżkę zamkniętą o tej własności nazywa się cyklem Hamiltona, a graf ją zawierający – grafem hamiltonowskim[1][2][3]. Graf niehamiltonowski, ale posiadający ścieżkę Hamiltona nazywa się czasem półhamiltonowskim[1].
W przeciwieństwie do grafów eulerowskich, nie jest znana (i prawdopodobnie nie istnieje[2]) prosta charakteryzacja tych grafów, które zawierają cykl Hamiltona[2][3]. Problem rozstrzygnięcia, czy graf jest hamiltonowski nie ma znanego efektywnego algorytmu rozwiązywania, co więcej jest to problem NP-zupełny[4][3][5].
Wymienione tu pojęcia noszą nazwisko Williama Hamiltona, który zaproponował grę polegającą na znalezieniu cyklu wzdłuż krawędzi dwunastościanu foremnego[1][4]. Problem cykli Hamiltona w grafach wielościanów był jednak badany już rok wcześniej przez Thomasa Kirkmana(inne języki), który podał między innymi przykład wielościanu bez cykli Hamiltona[6]. 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[7].
- Dwunastościan foremny z zaznaczonym przykładowym rozwiązaniem gry Hamiltona.
- Ten sam cykl zaznaczony w grafie płaskim dwunastościanu foremnego.
Przykłady
Z reguły przyjmuje się, że – graf o jednym wierzchołku jest hamiltonowski. Liczba grafów hamiltonowskich o wierzchołkach jest równa odpowiednio[8]:
- 1, 0, 1, 3, 8, 48, 383, … (ciąg
A003216 w OEIS).
Niektóre klasy grafów mają tę własność, że wszystkie należące do nich grafy są hamiltonowskie[8]:
- graf pełny o co najmniej trzech wierzchołkach,
- pełny graf dwudzielny o co najmniej czterech wierzchołkach,
- -kostka dla
- koło dla
- grafy platońskie (wielościanów foremnych)[9],
- grafy wielościanów półforemnych[9].
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[10].
![Rysunek grafu Herschela na płaszczyźnie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Herschel_graph_no_col.svg/200px-Herschel_graph_no_col.svg.png)
![Animowany wielościan Herschela](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Herschel_enneahedron_animated.gif/200px-Herschel_enneahedron_animated.gif)
Zobacz też
- cykl Eulera
- problem komiwojażera
Przypisy
- ↑ a b c RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 53-56, ISBN 978-83-01-15066-2 (pol.).
- ↑ a b c ReinhardR. Diestel ReinhardR., Graph Theory, Berlin: Springer, 2017, s. 307–322, ISBN 978-3-662-53621-6 (ang.).
- ↑ a b c KennethK. Ross KennethK., CharlesCh. Wright CharlesCh., Matematyka dyskretna, Wydawnictwo Naukowe PWN, 2012, s. 372-379, ISBN 978-83-01-14380-0 (pol.).
- ↑ a b graf Hamiltona, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2024-04-21] .
- ↑ MichaelM. Garey MichaelM., DavidD. Johnson DavidD., Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: Freeman, 1979, s. 60, ISBN 978-0-7167-1045-5 (ang.).
- ↑ N.L.N.L. Biggs N.L.N.L., T. P. Kirkman, Mathematician, „Bulletin of the London Mathematical Society”, 13 (2), 1981, s. 97–120, DOI: 10.1112/blms/13.2.97 [dostęp 2024-04-21] (ang.).
- ↑ JohnJ. Watkins JohnJ., Across the board: the mathematics of chessboard problems, Princeton University Press, 2004, s. 25-38, ISBN 978-0-691-15498-5 (ang.).
- ↑ a b Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Graph [online], Wolfram MathWorld [dostęp 2024-04-28] (ang.).
- ↑ a b MartinM. Gardner MartinM., Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi., „Scientific American”, 196 (5), 1957, s. 150–157, DOI: 10.1038/scientificamerican0557-150, ISSN 0036-8733 [dostęp 2024-04-28] (ang.).
- ↑ Eric W.E.W. Weisstein Eric W.E.W., Herschel Graph [online], Wolfram MathWorld [dostęp 2024-04-28] (ang.).
Linki zewnętrzne
Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Cycle, [w:] MathWorld, Wolfram Research [dostęp 2024-04-28] (ang.).
- Britannica: topic/Hamilton-circuit