맨위로가기

해밀턴 경로

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

해밀턴 경로는 그래프의 모든 꼭짓점을 한 번씩 방문하는 경로이며, 해밀턴 순환은 해밀턴 경로인 순환을 의미한다. 해밀턴 순환을 포함하는 그래프는 해밀턴 그래프, 해밀턴 경로를 포함하는 그래프는 추적 가능한 그래프라고 한다. 해밀턴 경로 또는 사이클을 찾는 문제는 NP-완전 문제이며, 그래프의 차수와 관련된 여러 정리들이 해밀턴 그래프 여부를 판별하는 데 사용된다. 윌리엄 로언 해밀턴은 1857년 정십이면체 그래프에서 해밀턴 순환을 찾는 문제를 제안했다.

더 읽어볼만한 페이지

  • 해밀턴 경로 - 외판원 문제
    외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다.
  • 해밀턴 경로 - 기사의 여행
    기사의 여행은 체스판에서 나이트가 각 칸을 한 번씩 방문하는 경로를 찾는 수학 문제로, 오일러를 비롯한 다양한 분야의 사람들이 연구에 기여했으며, 체스판 크기에 따라 해답 존재 여부가 달라지고 다양한 알고리즘으로 해결 가능하다.
  • 윌리엄 로언 해밀턴 - 해밀토니언 (양자역학)
    양자역학에서 해밀토니언은 계의 총 에너지를 나타내는 연산자로서, 고전역학의 해밀토니안에서 유래하며 슈뢰딩거 방정식을 통해 계의 시간적 진화를 결정하고, 그 고유값은 허용된 에너지 준위를 나타낸다.
  • 윌리엄 로언 해밀턴 - 해밀턴의 원리
    해밀턴의 원리는 일반화 좌표계에서 계의 변화가 작용 범함수의 극값을 가지며, 라그랑지안을 시간으로 적분한 작용을 통해 기술되고, 오일러-라그랑주 방정식과의 동등성을 가지며 다양한 물리적 현상 기술에 적용된다.
  • 그래프 이론의 계산 문제 - 외판원 문제
    외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다.
  • 그래프 이론의 계산 문제 - 부합 (그래프 이론)
    부합은 그래프 이론에서 서로 인접하지 않는 변들의 집합으로, 최대 부합은 변의 수가 가장 많은 부합이며, 그래프의 모든 정점을 매칭하는 부합을 완전 매칭이라고 한다.
해밀턴 경로
정의
설명그래프에서 각 정점을 정확히 한 번씩 방문하는 경로이다.
속성
존재 여부 결정NP-완전 문제이다. 즉, 주어진 그래프에 해밀턴 경로가 존재하는지 여부를 효율적으로 판단하는 알고리즘은 아직 발견되지 않았다.
방향 그래프방향 그래프의 해밀턴 경로는 모든 방향 간선을 따라 각 정점을 정확히 한 번씩 방문하는 경로이다.
응용집합 덮개 문제
최대 절단 문제
여행하는 외판원 문제
예시
그래프완전 그래프는 항상 해밀턴 경로를 가진다.
체스판나이트 투어는 체스판에서 나이트가 모든 칸을 한 번씩 방문하는 경로이며, 이는 해밀턴 경로의 한 예이다.

2. 정의

그래프에서 모든 꼭짓점을 한 번씩만 지나는 경로를 해밀턴 경로라고 한다. 해밀턴 순환은 해밀턴 경로이면서 순환인 경우를 말한다.

해밀턴 순환을 갖는 그래프는 해밀턴 그래프, 해밀턴 경로를 갖는 그래프는 자취 존재 그래프라고 부른다.

2. 1. 관련 용어


  • '''경로''': 그래프에서 꼭짓점들이 연결된 순서를 나타내며, 한 꼭짓점에서 다른 꼭짓점으로 이동하는 방법을 나타낸다.
  • '''순환''' (사이클): 시작 꼭짓점과 끝 꼭짓점이 같은 경로를 의미한다.
  • '''유향 그래프''': 간선(호)이 단일 방향으로만 추적될 수 있는 그래프이다.
  • '''해밀턴 분해''': 그래프를 해밀턴 회로로 분해하는 간선 분해이다.[3][4]

3. 성질

모든 해밀턴 사이클은 그 모서리 중 하나를 제거하여 해밀턴 경로로 변환될 수 있지만, 해밀턴 경로는 그 끝점이 인접한 경우에만 해밀턴 사이클로 확장될 수 있다.

모든 해밀턴 그래프는 이중 연결 그래프이지만, 이중 연결 그래프가 반드시 해밀턴 그래프일 필요는 없다. 예를 들어, 피터슨 그래프는 이중 연결 그래프이지만 해밀턴 그래프가 아니다.[9]

오일러 그래프는 모든 꼭짓점이 짝수 차수를 갖는 연결 그래프이므로, 반드시 오일러 투어(각 모서리를 정확히 한 번씩 통과하는 폐쇄된 걷기)를 갖는다. 이 투어는 선 그래프에서 해밀턴 사이클에 해당하므로 모든 오일러 그래프의 선 그래프는 해밀턴 그래프이다. 선 그래프는 오일러 투어에 해당하지 않는 다른 해밀턴 사이클을 가질 수 있으며, 특히 모든 해밀턴 그래프의 선 그래프는 그래프가 오일러인지 여부에 관계없이 자체적으로 해밀턴 그래프이다.[10]

토너먼트 (세 개 이상의 꼭짓점을 가진)는 강하게 연결되어 있을 때만 해밀턴 그래프이다.

n개의 꼭짓점을 가진 완전 무방향 그래프에서 서로 다른 해밀턴 사이클의 수는 (n-1)!/2이고, n개의 꼭짓점을 가진 완전 방향 그래프에서 서로 다른 해밀턴 사이클의 수는 (n-1)!이다. 이 개수는 시작점만 다른 동일한 사이클을 별도로 계산하지 않는다고 가정한다.

3. 1. 본디-흐바탈 정리

'''본디-흐바탈 정리'''(Bondy–Chvátal theorem영어)에 따르면, 유한 그래프 G가 해밀턴 그래프일 필요충분조건은 G의 폐포가 해밀턴 그래프인 것이다.[11] 폐포는 완전 그래프에 가까울수록 해밀턴 그래프일 가능성이 높다는 것을 시사한다.

그래프 G의 '''폐포'''(closure영어) \operatorname{cl}(G)는 G와 같은 꼭짓점들을 가지며, G의 간선들을 모두 포함하고, 임의의 두 꼭짓점 u, v에 대해 u와 v가 연결되어 있지만 uv가 \operatorname{cl}(G)의 간선이 아니라면 \deg u+\deg v (n은 꼭짓점의 개수)인 가장 작은 그래프이다.

본디-흐바탈 정리는 1972년 본디와 흐바탈이 디랙(1952)과 오레(1960)의 이전 결과를 일반화하여 만들었다.[11] 이 정리는 포사 정리(1962)에서 파생될 수 있다.[11]

3. 1. 1. 디랙의 정리

크기가 3 이상인 유한 그래프에서 모든 꼭짓점의 차수가 꼭짓점 개수의 절반 이상이면 그 그래프는 해밀턴 그래프이다. 이 정리는 가브리엘 앤드루 디랙(G. A. Dirac)이 1952년에 증명하였다.[11]

3. 1. 2. 오레의 정리

외위스테인 오레가 1960년에 증명한 오레의 정리는 다음과 같다.[11]

:크기가 3 이상인 단순 그래프에서, 인접하지 않은 모든 꼭짓점 쌍의 차수 합이 꼭짓점 개수 이상이면 그 그래프는 해밀턴 그래프이다.

이 정리는 그래프에 '충분한 간선'이 있다면 해밀턴 그래프가 된다는 것을 보여준다.[11]

3. 1. 3. Ghouila–Houiri의 정리 (유향 그래프)

개의 정점을 가진 강결합 그래프 단순 그래프 유향 그래프는 모든 정점이 전체 차수가 이상이면 해밀턴 그래프이다.[11]

3. 1. 4. Meyniel의 정리 (유향 그래프)

개의 정점을 가진 강결합 그래프 단순 그래프 유향 그래프에서, 서로 다른 모든 비인접 정점 쌍의 전체 차수 합이 2n-1 이상이면 해밀턴 그래프이다.[11]

3. 1. 5. Rahman–Kaykobad의 정리

Rahman–Kaykobad영어의 정리에 따르면, 크기가 n인 단순 그래프에서 모든 비인접 정점 쌍에 대해 차수와 최단 경로 길이의 합이 n보다 크면 해밀턴 경로를 가진다.[12]

4. 알고리즘

어떤 그래프가 자취 존재 그래프인지 여부를 묻는 결정 문제는 '''해밀턴 경로 문제'''라고 하며, NP-완전 문제이다. 마찬가지로, 어떤 그래프가 해밀턴 그래프인지 여부를 묻는 결정 문제는 '''해밀턴 순환 문제'''라고 하며, 역시 NP-완전 문제이다. 유향 그래프에 대한 마찬가지 결정 문제 역시 NP-완전 문제이다.

몬테카를로 방법을 사용하면, n개의 꼭짓점을 갖는 그래프의 해밀턴 순환 문제는 O(1.657^n)에 풀 수 있으며, 이분 그래프의 해밀턴 순환 문제는 O(1.414^n)에 풀 수 있다.[17] 퇴각검색 알고리즘을 사용하면, 삼차 그래프의 해밀턴 순환 문제는 O(1.251^n)의 시간으로 풀 수 있다.[18]

5. 예

기사 그래프. 기사의 여행 문제는 기사 그래프의 해밀턴 경로 또는 해밀턴 순환을 찾는 문제이다.


기사 그래프 위의 해밀턴 순환


기사의 여행 문제는 64개의 꼭짓점을 갖는 '''기사 그래프'''(knight’s graph영어)에서 해밀턴 경로와 해밀턴 순환을 찾는 문제이다. 이 그래프는 8×8 체스판에서 나이트가 움직일 수 있는 방향들을 변으로 한다.

다음과 같은 그래프들은 해밀턴 그래프이다.

다음과 같은 그래프들은 해밀턴 그래프가 아니다.

  • 비연결 그래프
  • 트리 그래프


다음과 같은 그래프는 자취 존재 그래프이지만 해밀턴 그래프가 아니다.

6. 역사

윌리엄 로언 해밀턴이 1857년에 정십이면체 그래프 위의 해밀턴 순환을 찾는 문제를 제안하였다. 해밀턴은 이 문제를 아이코시언 게임(icosian game|아이코시언 게임영어)이라고 불렀다.

참조

[1] 간행물 T. P. Kirkman, mathematician
[2] 서적 Across the Board: The Mathematics of Chessboard Problems Princeton University Press
[3] 서적 Hamilton Mazes – The Beginner's Guide 2017
[4] 웹사이트 Hamiltonian Mazes http://www2.stetson.[...] 2009
[5] 뉴스 Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi. http://www.scientifi[...] Gardner, M. Sci. Amer. 1957-05
[6] 간행물 Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian 2014
[7] 간행물 The rotation graph of binary trees is Hamiltonian
[8] 간행물 Graph of triangulations of a convex polygon and tree of triangulations
[9] 웹사이트 Biconnected Graph http://mathworld.wol[...] Wolfram MathWorld
[10] 서적 A Textbook of Graph Theory https://books.google[...] Springer
[11] 웹사이트 Advances on the Hamiltonian Problem – A Survey http://www.mathcs.em[...] Emory University 2002-07-08
[12] 간행물 On Hamiltonian cycles and Hamiltonian paths 2005-04
[13] 간행물 On Hamiltonian bipartite graphs
[14] 간행물 A theorem on graphs
[15] 간행물 A theorem on planar graphs
[16] 서적 Proceedings of 37th Conference on Foundations of Computer Science
[17] 서적 Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10)
[18] 서적 Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007)


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com