해밀턴 경로

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
정십이면체의 모든 꼭짓점을 지나는 해밀턴 순환

그래프 이론에서, 해밀턴 경로(Hamilton經路, 영어: Hamiltonian path)는 모든 꼭짓점을 한 번씩 지나는 경로이다.

정의[편집]

그래프 G해밀턴 경로 pG의 모든 꼭짓점을 포함하는 경로이다. (정의에 따라, 경로는 꼭짓점을 중복하여 거치지 않는 보행이다.) 해밀턴 순환(영어: Hamiltonian cycle)은 해밀턴 경로인 순환이다.

해밀턴 순환을 갖는 그래프를 해밀턴 그래프(영어: Hamiltonian graph)라고 한다. 해밀턴 경로를 갖는 그래프를 자취 존재 그래프(영어: traceable graph)라고 한다.

성질[편집]

유한 그래프 G폐포(영어: closure) \operatorname{cl}(G)는 다음 성질들을 만족시키는 가장 작은 그래프이다.

  • V(\operatorname{cl}(G))=V(G)
  • E(\operatorname{cl}(G))\supset E(G)
  • 임의의 u,v\in V(\operatorname{cl}(G))에 대하여, uv가 같은 연결 성분에 속하지만 uv\not\in E(\operatorname{cl}(G))라면 \deg u+\deg v<n

이러한 그래프는 유일함을 보일 수 있다.

본디-흐바탈 정리(영어: Bondy–Chvátal theorem)에 따르면, 유한 그래프 G에 대하여 다음 두 조건이 서로 동치이다.

  • G는 해밀턴 그래프이다.
  • G의 폐포는 해밀턴 그래프이다.

특히, 크기가 3 이상인 완전 그래프는 해밀턴 그래프이므로, 폐포가 완전 그래프인 그래프는 해밀턴 그래프이다. 즉, 다음과 같은 따름정리를 얻을 수 있다. 모든 유한 그래프 G에 대하여, 만약 |V(G)|\ge3라면 다음이 성립한다.

  • (디랙의 정리 영어: Dirac’s theorem) 만약 \deg v\ge|V(G)|/2라면 G는 해밀턴 그래프이다.
  • (오레의 정리 영어: Ore’s theorem) 만약 모든 인접하지 않은 꼭짓점 u,v\in V(G)에 대하여 \deg x+\deg y\ge|V(G)|라면, G는 해밀턴 그래프이다.

디랙의 정리는 디랙(영어: G. A. Dirac)이 1952년에 증명하였다. 오레의 정리는 외위스테인 오레(노르웨이어: Øystein Ore)가 1960년에 증명하였다.

알고리즘[편집]

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

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

[편집]

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

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

해밀턴 그래프의 예[편집]

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

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

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

역사[편집]

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

참고 문헌[편집]

  1. (영어) Björklund, Andreas (2010년). 〈Determinant sums for undirected Hamiltonicity〉, 《Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10)》, 173–182쪽. arXiv:1008.0541. doi:10.1109/FOCS.2010.24. ISBN 978-1-4244-8525-3
  2. (영어) Iwama, Kazuo, Takuya Nakashima (2007년). 〈An improved exact algorithm for cubic graph TSP〉, 《Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007)》, Lecture Notes in Computer Science 4598, 108–117쪽. doi:10.1007/978-3-540-73545-8_13. ISBN 978-3-540-73544-1

바깥 고리[편집]

같이 보기[편집]