해밀턴 회로

1. 개요[편집]

---

아일랜드 출신의 수학자 윌리엄 로원 해밀턴이 그래프 이론에 제기한 회로의 종류이다. 기본적으로 해밀턴 경로는 어떤 연결된 그래프에서 모든 꼭짓점을 한 번씩만 지나는 경로를 부르는 말이다. 또한 이 경로가 회로일 경우 해밀턴 회로라고 하며, 어떤 그래프가 해밀턴 회로를 가질 때, 이 그래프를 해밀턴 그래프라고 한다. 오일러 회로와 같이 다루기도 한다.

2. 오일러 회로와의 비교[편집]

---

오일러 회로란 연결된 그래프의 모든 변을 중복 없이 지나는 회로로, 익히 알려진 한붓그리기로 그려진 회로를 의미한다. 여기서 중요한 것은 변으로, 어떤 꼭짓점은 2회 이상 지나는 것에 대해서는 신경쓰지 않는다. 그래프 이론에서는 트레일(trail)에 가깝다.

해밀턴 회로는 그 반대이다. 여기서는 모든 변을 지날 필요가 없지만, 한 꼭짓점은 단 한 번만 지나야한다. 그래프 이론의 패스(path)이다.

길이로 비교하자면, 오일러 그래프이자 해밀턴 그래프인 [math(G)]에 대해 해밀턴 회로의 길이는 [math(n(V(G)))]이며, 오일러 그래프의 길이는 [math(n(E(G)))]이다.

오일러 그래프이면서 동시에 해밀턴 그래프일 수 있고[1], 둘 중 한 쪽에만 해당될 수도 있으며, 둘 다 아닐 수도 있다. 즉, 오일러 그래프와 해밀턴 그래프 사이에는 관계가 없다.

3. 필요충분조건[편집]

---

알려져 있지 않다. 어떤 연결된 그래프가 오일러 그래프이기 위한 필요충분조건은 알려져 있지만, 해밀턴 회로의 경우 그렇지 않다. 그렇기에 현재 해밀턴 회로를 가지는 그래프의 조건을 알아내고, 해밀턴 회로를 찾는 방법을 구하는 것은 그래프 연구의 중요한 문제 중 하나이다.

3.1. 필요조건[편집]

---

• 필요조건이라 알려진 것은 전부 해밀턴 회로가 지니고 있는 성질을 나열하거나 변형한 것 뿐이라 그래프를 좁힐 수 없다.

차수가 [math(n)]인 연결그래프 [math(G)]에 대하여 이 그래프가 해밀턴 회로 [math(H)]라면 다음 성질을 만족한다.

• [math(|H|=n)]
• 각 꼭짓점에 인접한 변 중에서 오직 두 변만이 [math(H)]에 포함된다. 따라서, 차수가 2인 꼭짓점에 인접한 변은 모두 [math(H)]에 포함된다.[2]
  해밀턴 회로는 모든 점을 한번씩만 지나야 하기 때문에 해밀턴 회로의 모든 꼭짓점에서의 차수는 무조건 2 이하가 된다.
• [math(H)]의 일부만으로 구성되는 회로는 존재하지 않는다.
• 꼭짓점 [math(v)]가 [math(H)]에 포함되어 있다면, [math(v)]에 인접한 변 중에서 [math(H)]에 포함되지 않은 변은 소거하더라도 [math(H)]를 찾는데는 문제가 발생하지 않는다.

3.2. 충분조건[편집]

---

• 오레의 정리(Ore's theorem): [math( n(V(G)) = n \ge 3 )]인 그래프 [math(G)]와 [math(u, v \in V(G))]인 임의의 서로 다른 두 꼭짓점 [math(u, v)]에 대해 [math( \displaystyle deg(u) + deg(v) \ge n )]이면 [math(G)]는 해밀턴 회로를 갖는다.[3]
  같은 조건의 그래프 G에 대해 임의의 꼭짓점의 차수가 n/2 이상이어도 성립한다.