Ścieżka Hamiltona

Ś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. Graf niehamiltonowski, ale posiadający ścieżkę Hamiltona nazywa się czasem półhamiltonowskim.

W przeciwieństwie do grafów eulerowskich, nie jest znana (i prawdopodobnie nie istnieje) prosta charakteryzacja tych grafów, które zawierają cykl Hamiltona. Problem rozstrzygnięcia, czy graf jest hamiltonowski nie ma znanego efektywnego algorytmu rozwiązywania, co więcej jest to problem NP-zupełny.

Wymienione tu pojęcia noszą nazwisko Williama Hamiltona, który zaproponował grę polegającą na znalezieniu cyklu wzdłuż krawędzi dwunastościanu foremnego. Problem cykli Hamiltona w grafach wielościanów był jednak badany już rok wcześniej przez Thomasa Kirkmana, który podał między innymi przykład wielościanu bez cykli Hamiltona. 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.

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 $K_{1}$ – graf o jednym wierzchołku jest hamiltonowski. Liczba grafów hamiltonowskich o $n=1,2,3\dots$ wierzchołkach jest równa odpowiednio:

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:

graf pełny $K_{n}$ o co najmniej trzech wierzchołkach,
pełny graf dwudzielny $K_{n,n}$ o co najmniej czterech wierzchołkach,
$n$ -kostka $Q_{n}$ dla $n\geq 2,$
koło $W_{n}$ dla $n\geq 4,$
grafy platońskie (wielościanów foremnych),
grafy wielościanów półforemnych.

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.

Graf Herschela oraz odpowiadający mu wielościan.

Zobacz też

Przypisy

1 2 3 RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 53-56, ISBN 978-83-01-15066-2 (pol.).
1 2 3 ReinhardR. Diestel ReinhardR., Graph Theory, Berlin: Springer, 2017, s. 307–322, ISBN 978-3-662-53621-6 (ang.).
1 2 3 KennethK. Ross KennethK., CharlesCh. Wright CharlesCh., Matematyka dyskretna, Wydawnictwo Naukowe PWN, 2012, s. 372-379, ISBN 978-83-01-14380-0 (pol.).
1 2 graf Hamiltona, [w:] Encyklopedia 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.).
1 2 Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Graph [online], Wolfram MathWorld [dostęp 2024-04-28] (ang.).
1 2 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.).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-1] 1 2 3 RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 53-56, ISBN 978-83-01-15066-2 (pol.).

[:1-2] 1 2 3 ReinhardR. Diestel ReinhardR., Graph Theory, Berlin: Springer, 2017, s. 307–322, ISBN 978-3-662-53621-6 (ang.).

[:2-3] 1 2 3 KennethK. Ross KennethK., CharlesCh. Wright CharlesCh., Matematyka dyskretna, Wydawnictwo Naukowe PWN, 2012, s. 372-379, ISBN 978-83-01-14380-0 (pol.).

[:3-4] 1 2 graf Hamiltona, [w:] Encyklopedia PWN [dostęp 2024-04-21] .

[5] 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.).

[6] 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.).

[7] 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.).

[:4-8] 1 2 Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Graph [online], Wolfram MathWorld [dostęp 2024-04-28] (ang.).

[:5-9] 1 2 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.).

[10] Eric W.E.W. Weisstein Eric W.E.W., Herschel Graph [online], Wolfram MathWorld [dostęp 2024-04-28] (ang.).