해밀턴 경로

6개의 정점으로 이루어진 네트워크 주위의 해밀턴 사이클

그래프 이론의 수학 분야에서, 해밀턴 경로(또는 추적 가능한 경로)는 각 정점을 정확히 한 번 방문하는 무방향 또는 방향 그래프의 경로이다.해밀턴 사이클(또는 해밀턴 회로)은 각 정점을 정확히 한 번 방문하는 사이클입니다.인접한 정점에서 시작하고 끝나는 해밀턴 경로는 해밀턴 사이클을 형성하기 위해 에지를 하나 더 추가하면 완성될 수 있으며, 해밀턴 사이클에서 에지를 제거하면 해밀턴 경로가 생성됩니다.이러한 경로와 사이클이 그래프에 존재하는지 여부를 결정하는 것은 NP-완전입니다(해밀턴 경로 문제 및 해밀턴 사이클 문제).

해밀턴의 경로와 순환은 현재 해밀턴의 퍼즐로도 알려진 이코시안 게임을 발명한 윌리엄 로완 해밀턴의 이름을 따왔다. 이 게임은 12면체의 모서리 그래프에서 해밀턴의 순환을 찾는 것을 포함한다.해밀턴은 이 문제를 아이코시안 미적분학을 사용하여 풀었는데, 이 구조는 4원소와 많은 유사점을 가진 단일성의 뿌리에 기초한 대수 구조이다.이 솔루션은 임의의 그래프로 일반화되지 않습니다.

해밀턴의 이름에서 따왔음에도 불구하고, 다면체의 해밀턴 순환은 토마스 커크먼에 의해 1년 전에 연구되었고, 그는 특히 해밀턴 ^[1]순환이 없는 다면체의 예를 제시했습니다.그보다 앞서, 체스판의 기사 그래프에 나오는 해밀턴의 순환과 경로는 9세기에 루드라타에 의해 인도 수학에서 연구되었고, 비슷한 시기에 알-아들리 아르-루미에 의해 이슬람 수학에서 연구되었다.18세기 유럽에서는 아브라함 드 모이브르와 레온하르트 ^[2]오일러에 의해 기사 투어가 출판되었다.

정의들

해밀턴 경로 또는 추적 가능한 경로는 그래프의 각 정점을 정확히 한 번 방문하는 경로입니다.해밀턴 경로를 포함하는 그래프를 추적 가능한 그래프라고 합니다.그래프는 모든 정점 쌍에 대해 두 정점 사이에 해밀턴 경로가 있는 경우 해밀턴으로 연결됩니다.

해밀턴 사이클, 해밀턴 회로, 정점 투어 또는 그래프 사이클은 각 정점을 정확히 한 번 방문하는 사이클입니다.해밀턴 순환을 포함하는 그래프를 해밀턴 그래프라고 합니다.

경로 또는 사이클의 각 가장자리(호)를 단방향으로만 추적할 수 있는 방향 그래프에도 유사한 개념을 정의할 수 있다(즉, 정점은 화살표로 연결되고 가장자리는 "꼬리 대 머리"로 추적된다).

해밀턴 분해는 그래프를 해밀턴 회로로 분해하는 것입니다.

해밀턴 미로는 주어진 ^[3]^[4]그래프에서 독특한 해밀턴 사이클을 찾는 것이 목표인 논리 퍼즐의 한 종류이다.

예

5개의 플라톤 솔리드 정점의 해밀턴 사이클이 있는 맞춤법 투영 및 슐레겔 다이어그램 - 8면체만 점으로 경로를 확장하여 오일러 경로 또는 사이클을 갖습니다.

두 개 이상의 정점이 있는 완전한 그래프는 해밀턴이다.
모든 주기 그래프는 해밀턴식이다.
모든 토너먼트에는 홀수 수의 해밀턴 경로가 있다(Rédei 1934).
그래프로 간주되는 모든 플라토닉 솔리드는 해밀턴이다^[5].
유한 콕서터 그룹의 케일리 그래프는 해밀턴이다(케일리 그래프의 해밀턴 경로에 대한 자세한 내용은 로바시즈 추측 참조).
순환 정류자 부분군이 있는 제로 효력 그룹에 대한 케일리 그래프는 해밀턴식입니다.^[6]
볼록 폴리곤의 플립 그래프 또는 이에 상당하는 이진수의 회전 그래프는 해밀턴이다.^[7]^[8]

특성.

허셜 그래프는 해밀턴 주기가 없는 가능한 가장 작은 다면체 그래프입니다.가능한 해밀턴 경로가 표시됩니다.

모든 해밀턴 사이클은 가장자리 중 하나를 제거함으로써 해밀턴 패스로 변환할 수 있지만, 해밀턴 패스는 끝점이 인접해 있는 경우에만 해밀턴 패스로 확장할 수 있습니다.

모든 해밀턴 그래프는 쌍커넥트되지만 쌍커넥트 그래프는 해밀턴 그래프일 필요는 없습니다(예: 피터슨 ^[9]그래프 참조).

오일러 $그래프$ G(모든 정점이 짝수 도를 갖는 연결 그래프)는 반드시 오일러 투어를 가지며, $오일러$ 의 각 모서리를 정확히 한 번 통과하는 닫힌 보행이다.이 둘러보기는 직선 $그래프$ L $(G)$ 의 해밀턴 주기에 해당하므로, 모든 오일러 그래프의 선 그래프는 해밀턴입니다.선 그래프는 오일러 투어에 대응하지 않는 다른 해밀턴 주기를 가질 수 있으며, 특히 $모든$ 해밀턴 $그래프$ G의 선 $그래프$ L $(G)$ 은 그래프 G가 ^[10]오일러인지 여부에 관계없이 그 자체로 해밀턴이다.

토너먼트(정점이 두 개 이상 있음)는 강하게 연결된 경우에만 해밀턴입니다.

다른 해밀턴 주기의 nvertices에 대한 완전한 지도자 없는 그래프의 번호 .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{.mw-parser-output 있다.디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-onlyᆬ(n– 1)!/2와 엔 vertices에 대한 완전한 직접적인 그래프에서(n– 1)..이러한 카운트는 시작점과 동일한 사이클이 별도로 카운트되지 않는다고 가정합니다.

본디-슈바르탈 정리

해밀턴 그래프의 최고의 정점 차수 특성화는 1972년에 G. A. 디락(1952)과 외이슈타인 오레의 초기 결과를 일반화한 본디-슈바탈 정리에 의해 제공되었다.디락과 오레의 정리 모두 포사의 정리(1962년)에서 도출할 수 있다.해밀턴시티는 그래프 밀도, 인성, 금지된 서브그래프 및 ^[11]다른 파라미터 간의 거리와 같은 다양한 파라미터와 관련하여 널리 연구되어 왔다.Dirac과 Ore의 이론은 기본적으로 그래프가 충분한 모서리를 가지고 있다면 해밀턴이라고 기술한다.

Bondy-Chvatal 정리는 n개의 $정점$ 이 있는 $그래프$ G의 $폐쇄$ cl(G $)$ 에 대해 작동하며, 이 성질을 가진 쌍이 더 이상 발견되지 않을 때까지 deg $(v)$ + $deg$ ( $u) δ n$ 으로 $연결$ 된 새로운 $가장자리$ uv를 반복적으로 추가한다.

본디-치바탈 정리(1976) — 그래프는 폐색이 해밀턴인 경우에만 해밀턴이다.

완전한 그래프는 해밀턴이므로, 폐색된 그래프는 모두 해밀턴이며, 이는 디락과 오레가 작성한 다음의 초기 이론의 내용이다.

Dirac의 정리(1952) - n개의 $n\geq 3$ ( $n$ 3 \ $displaystyle$ n \ $geq$ 3 $)$ 이 $\tfrac{n}{2}$ $있는$ 단순한 그래프는 모든 꼭지점의 ${\tfrac {n}{2}}$ 가 n $(\$ $displaystyle$ \ $tfrac {n}$ {2 $}})$ 이상인 경우 해밀턴이 됩니다.

오레의 정리(1960) - n개의 정점( $n$ ( 3 \ $displaystyle$ n \ $geq$ 3 $n\geq 3$ 을 $갖는$ 단순한 그래프는 인접하지 않은 정점의 모든 쌍에 대해 각 차수의 $합$ 이 n 이상인 경우 해밀턴식이다.

다음 정리들은 지시된 버전으로 간주할 수 있습니다.

고일라Houiri(1960) - 모든 정점이 n보다 크거나 $같은$ 풀 도수를 갖는 경우 n개의 정점을 $가진$ 강하게 연결된 단순 방향 그래프는 해밀턴입니다.

Meyniel(1973) - N개의 정점을 $가진$ 강하게 연결된 단순 방향 그래프는 인접한 정점의 모든 쌍의 전체 각도의 합계가 $2n-1$ $2n-1$ ({ $displaystyle 2n-1})$ $2n-1$ 일 경우 해밀턴이다.

각 무방향 모서리는 두 개의 방향 호에 해당하므로 정점 수는 두 배로 증가해야 합니다. 따라서 유방향 그래프의 정점 정도는 무방향 그래프의 두 배입니다.

Rahman-Kaykobad (2005) — 모든 비인접 정점 쌍에 대해 각 정도의 합이 ^[12]n보다 $크고$ 최단 경로 길이가 n보다 클 경우 n개의 정점이 있는 $단순$ 한 그래프는 해밀턴 경로를 가진다.

위의 정리는 그래프에서 해밀턴 경로의 존재만 인식할 수 있고 해밀턴 순환은 인식할 수 없습니다.

이러한 결과의 상당수는 균형 잡힌 초당 그래프에 대한 유사점을 가지고 있으며, 이 그래프에서는 정점 도수가 ^[13]전체 그래프에서 정점 수보다 초당 단일 면의 정점 수와 비교된다.

평면 그래프에 해밀턴 주기의 존재

정리 — 4연결 평면 삼각 측량에는 해밀턴 ^[14]사이클이 있습니다.

정리 - 4연결 평면 그래프는 ^[15]해밀턴 사이클을 가집니다.

해밀턴 순환 다항식

주어진 가중치 디그래프의 해밀턴 사이클의 대수적 표현(특정 지면장으로부터의 가중치가 할당되는 호)은 디그래프의 해밀턴 사이클의 아크 가중치 곱의 합으로 정의된 가중치 인접 행렬의 해밀턴 사이클 다항식이다.이 다항식은 이 그래프가 해밀턴식인 경우에만 호 가중치의 함수와 동일하게 0이 아닙니다.계산의 복잡성과 ^[16]영구 계산의 관계는 그리고리 코건에 의해 증명되었습니다.

「」를 참조해 주세요.

바르넷의 추측, 입방정초 다면체 그래프의 해밀턴성에 대한 미해결 문제
그래프의 모든 모서리를 통과하는 경로인 오일러식 경로
해밀턴식 그래프에 대한 플라이슈너의 정리
그레이 코드
평면 그래프가 해밀턴 순환을 갖는 데 필요한 조건을 제공하는 그린버그의 정리
해밀턴 경로 문제, 해밀턴 경로를 찾는 계산 문제
하이포해밀턴 그래프, 모든 정점이 삭제된 하위 그래프가 해밀턴이 아닌 그래프
나이트 투어, 나이트 그래프에 있는 해밀턴 사이클
해밀턴 입방 그래프에 대한 LCF 표기법.
정점-추이 그래프가 해밀턴 그래프라는 로바시즈 추측
범순환 그래프, 해밀턴 사이클을 포함한 모든 길이의 사이클이 있는 그래프
쾨니히스베르크의 일곱 다리
Shortness 지수, 패밀리 내 그래프가 해밀턴으로부터 얼마나 멀리 떨어져 있을 수 있는지를 나타내는 수치적 척도
Snake-in-the-box, 하이퍼큐브에서 가장 긴 유도 경로
스타인하우스Johnson-Trotter 알고리즘: 반정면체에서 해밀턴 경로를 구함
평면 해밀턴 그래프의 서브그래프인 서브해밀턴 그래프
3정규 다면체 그래프가 해밀턴 그래프라는 Tait의 추측(지금은 거짓으로 알려져 있음)
출장 세일즈맨 문제

메모들

^ 를 클릭합니다Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093.
^ 를 클릭합니다Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5.
^ de Ruiter, Johan (2017). Hamilton Mazes – The Beginner's Guide.
^ Friedman, Erich (2009). "Hamiltonian Mazes". Erich's Puzzle Palace. Archived from the original on 16 April 2016. Retrieved 27 May 2017.
^ 가드너, M. "수학 게임: 이코시안 게임과 하노이 타워의 주목할 만한 유사성에 대하여." 과학.Amer. 196, 150-156, 1957년 5월
^ Ghaderpour, E.; Morris, D. W. (2014). "Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian". Ars Mathematica Contemporanea. 7 (1): 55–72. arXiv:1111.6216. doi:10.26493/1855-3974.280.8d3.
^ Lucas, Joan M. (1987), "The rotation graph of binary trees is Hamiltonian", Journal of Algorithms, 8 (4): 503–535, doi:10.1016/0196-6774(87)90048-4
^ Hurtado, Ferran; Noy, Marc (1999), "Graph of triangulations of a convex polygon and tree of triangulations", Computational Geometry, 13 (3): 179–188, doi:10.1016/S0925-7721(99)00016-4
^ Eric Weinstein. "Biconnected Graph". Wolfram MathWorld.
^ 를 클릭합니다Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of Graph Theory, Springer, p. 134, ISBN 9781461445296.
^ Gould, Ronald J. (July 8, 2002). "Advances on the Hamiltonian Problem – A Survey" (PDF). Emory University. Retrieved 2012-12-10.
^ Rahman, M. S.; Kaykobad, M. (April 2005). "On Hamiltonian cycles and Hamiltonian paths". Information Processing Letters. 94: 37–41. doi:10.1016/j.ipl.2004.12.002.
^ Moon, J.; Moser, L. (1963), "On Hamiltonian bipartite graphs", Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007/BF02759704, MR 0161332
^ Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003
^ Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8
^ Kogan, Grigoriy (1996), "Computing permanents over fields of characteristic 3: where and why it becomes difficult", 37th Annual Symposium on Foundations of Computer Science (FOCS '96): 108–114, doi:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2

레퍼런스

Berge, Claude; Ghouila-Houiri, A. (1962), Programming, games and transportation networks, New York: Sons, Inc.
를 클릭합니다DeLeon, Melissa (2000), "A study of sufficient conditions for Hamiltonian cycles" (PDF), Rose-Hulman Undergraduate Math Journal, 1 (1), archived from the original (PDF) on 2012-12-22, retrieved 2005-11-28.
를 클릭합니다Dirac, G. A. (1952), "Some theorems on abstract graphs", Proceedings of the London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112/plms/s3-2.1.69, MR 0047308.
를 클릭합니다Hamilton, William Rowan (1856), "Memorandum respecting a new system of roots of unity", Philosophical Magazine, 12: 446.
를 클릭합니다Hamilton, William Rowan (1858), "Account of the Icosian Calculus", Proceedings of the Royal Irish Academy, 6: 415–416.
를 클릭합니다Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté", Journal of Combinatorial Theory, Series B, 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9, MR 0317997.
를 클릭합니다Ore, Øystein (1960), "Note on Hamilton circuits", The American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, MR 0118683.
를 클릭합니다Pósa, L. (1962), "A theorem concerning Hamilton lines", Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226, MR 0184876.

외부 링크

[1] 를 클릭합니다Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093.

[2] 를 클릭합니다Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5.

[3] Ruiter, Johan (2017). Hamilton Mazes – The Beginner's Guide.

[4] Friedman, Erich (2009). "Hamiltonian Mazes". Erich's Puzzle Palace. Archived from the original on 16 April 2016. Retrieved 27 May 2017.

[5] 가드너, M. "수학 게임: 이코시안 게임과 하노이 타워의 주목할 만한 유사성에 대하여." 과학.Amer. 196, 150-156, 1957년 5월

[6] Ghaderpour, E.; Morris, D. W. (2014). "Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian". Ars Mathematica Contemporanea. 7 (1): 55–72. arXiv:1111.6216. doi:10.26493/1855-3974.280.8d3.

[7] Lucas, Joan M. (1987), "The rotation graph of binary trees is Hamiltonian", Journal of Algorithms, 8 (4): 503–535, doi:10.1016/0196-6774(87)90048-4

[8] Hurtado, Ferran; Noy, Marc (1999), "Graph of triangulations of a convex polygon and tree of triangulations", Computational Geometry, 13 (3): 179–188, doi:10.1016/S0925-7721(99)00016-4

[9] Eric Weinstein. "Biconnected Graph". Wolfram MathWorld.

[10] 를 클릭합니다Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of Graph Theory, Springer, p. 134, ISBN 9781461445296.

[11] Gould, Ronald J. (July 8, 2002). "Advances on the Hamiltonian Problem – A Survey" (PDF). Emory University. Retrieved 2012-12-10.

[12] Rahman, M. S.; Kaykobad, M. (April 2005). "On Hamiltonian cycles and Hamiltonian paths". Information Processing Letters. 94: 37–41. doi:10.1016/j.ipl.2004.12.002.

[13] Moon, J.; Moser, L. (1963), "On Hamiltonian bipartite graphs", Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007/BF02759704, MR 0161332

[14] Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003

[15] Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8

[16] Kogan, Grigoriy (1996), "Computing permanents over fields of characteristic 3: where and why it becomes difficult", 37th Annual Symposium on Foundations of Computer Science (FOCS '96): 108–114, doi:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Search

해밀턴 경로

네임스페이스

더

목차

정의들

예

특성.

본디-슈바르탈 정리

평면 그래프에 해밀턴 주기의 존재

해밀턴 순환 다항식

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

해밀턴 경로

정의들

예

특성.

본디-슈바르탈 정리

평면 그래프에 해밀턴 주기의 존재

해밀턴 순환 다항식

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.