해밀턴 회로
1. 개요
아일랜드 출신의 수학자 윌리엄 로원 해밀턴이 그래프 이론에 제기한 회로의 종류이다. 기본적으로 해밀턴 경로는 어떤 연결된 그래프에서 모든 꼭짓점을 한 번씩만 지나는 경로를 부르는 말이다. 또한 이 경로가 회로일 경우 해밀턴 회로라고 하며, 어떤 그래프가 해밀턴 회로를 가질 때, 이 그래프를 해밀턴 그래프라고 한다. 오일러 회로와 같이 다루기도 한다.
2. 오일러 회로와의 비교
오일러 회로란 연결된 그래프의 모든 변을 중복 없이 지나는 회로로, 익히 알려진 한붓그리기로 그려진 회로를 의미한다. 여기서 중요한 것은 '''변'''으로, 어떤 꼭짓점은 2회 이상 지나는 것에 대해서는 신경쓰지 않는다. 그래프 이론에서는 트레일(trail)에 가깝다.
해밀턴 회로는 그 반대이다. 여기서는 모든 변을 지날 필요가 없지만, '''한 꼭짓점은 단 한 번만 지나야한다.''' 그래프 이론의 패스(path)이다.
길이로 비교하자면, 오일러 그래프이자 해밀턴 그래프인 $$G$$에 대해 해밀턴 회로의 길이는 $$n(V(G))$$이며, 오일러 그래프의 길이는 $$n(E(G))$$이다.
오일러 그래프이면서 동시에 해밀턴 그래프일 수 있고[1], 둘 중 한 쪽에만 해당될 수도 있으며, 둘 다 아닐 수도 있다. 즉, '''오일러 그래프와 해밀턴 그래프 사이에는 관계가 없다.'''
3. 필요충분조건
알려져 있지 않다. 어떤 연결된 그래프가 오일러 그래프이기 위한 필요충분조건은 알려져 있지만, 해밀턴 회로의 경우 그렇지 않다. 그렇기에 현재 해밀턴 회로를 가지는 그래프의 조건을 알아내고, 해밀턴 회로를 찾는 방법을 구하는 것은 그래프 연구의 중요한 문제 중 하나이다.
3.1. 필요조건
3.2. 충분조건
- $$ n(V(G)) = n \ge 3 $$인 그래프 $$G$$와 $$u, v \in V(G)$$인 임의의 서로 다른 두 꼭짓점 $$u, v$$에 대해 $$ \displaystyle deg(u) + deg(v) \ge n $$이면 $$G$$는 해밀턴 회로를 갖는다.[2]