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

Graf o sześciu wierzchołkach z zaznaczonym cyklem Hamiltona. — Graf hamiltonowski z wyróżnionym na czerwono cyklem Hamiltona.

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 edytuj

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

Graf Herschela oraz odpowiadający mu wielościan.

Zobacz też edytuj

Przypisy edytuj

↑ ^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 [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 edytuj

Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Cycle, [w:] MathWorld, Wolfram Research [dostęp 2024-04-28] (ang.).

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

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

[: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] 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] Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Graph [online], Wolfram MathWorld [dostęp 2024-04-28] (ang.).

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]