해밀턴 경로

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

그래프 이론에서, 해밀턴 경로(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. 

바깥 고리[편집]

같이 보기[편집]