Hamiltonian Cycles  and  Travelling Salesperson Problem

이산수학 : Richard Johnsonbaugh 저서, 강홍식.김정인.이도훈.이명재 번역, 교보문고, 1999 (원서 : Discrete Mathematics 6th ed, Prentice-Hall, 1997), Page 394~400

윌리엄 로완 해밀턴 (William Rowan Hamilton) 경은 1800 년 중반 12 면체의 모양에서 수수께끼 하나를 제시했다 (그림 1 참조). 각 꼭지점에 도시 이름을 주고, 문제는 어떤 도시에서 출발하여, 간선들을 따라서 한 도시를 한번만 방문하여, 최초의 출발 도시로 돌아오는 것이다. 12 면체의 간선의 그래프는 그림 2 에 주어져 있다. 해밀턴의 수수께끼를 그림 2 의 그래프에서 사이클을 찾을 수 있다면 문제는 해결된다. 다만 각 정점은 한 번만 포함되어야 한다 (출발점과 끝나는 점은 두 번 나타나는 것을 제외하고). 그림 3 에 주어진 해를 보기전에 스스로 문제의 해를 찾아보라.

그림 1  해밀턴 퍼즐

그림 2  해밀턴 퍼즐의 그래프

그림 3  그림 2 의 그래프에서 각 정점이 한번만 방문한다.

해밀턴의 업적을 기리어, 주어진 그래프에서 출발점과 종료점만 두 번 나타나는 것을 제외하고는 정점이 한 번씩만 나타나는 사이클을 해밀턴 사이클 (Hamiltonian cycle) 이라 한다.

해밀턴 (1805~1865)은 아일랜드의 대학자였다. 그는 듀브린 대학의 천문학 교수였고, 물리학과 수학 분야에서 많은 논문들을 집필했다. 수학 분야에서, 해밀턴은 사원법 (quaternions) 의 발명, 실수 체계의 일반화로 매우 유명하다. 그의 사원법은 현대 추상 대수의 발전에 영감을 주었다. 해밀턴은 벡터 용어를 도입했다.

 (예제 3.1)  

사이클 (a, b, c, d, e, f, g, a) 은 그림 4 의 그래프에서 해밀턴 사이클이다.

해밀턴 사이클을 찾는 문제는 그래프에서 오일러 사이클을 찾는 문제와 매우 유사해 보인다. 오일러 사이클은 각 간선을 한 번씩 방문하는 반면, 해밀턴 사이클은 각 정점을 한 번만 방문한다 ; 하지만 이 문제들은 실제 상당히 다른 문제이다. 예를 들어, 그림 4 의 그래프 G 는 홀수 차수의 정점들이 존재하기 때문에 오일러 사이클이 존재하지 않는다, 예제 1 은 G 가 해밀턴 사이클을 갖는 것을 보였다. 더 나아가 오일러 사이클에 대한 상황과는 다르게 (정리 2.17 과 2.18 참조), 그래프에서 해밀턴 사이클이 존재하기 위한 필요 충분 조건들은 쉽게 입증되지 않는다.

그림 4  해밀턴 사이클을 가지는 그래프

다음 예제들은 어떤 그래프가 해밀턴 사이클을 포함하고 있지 않다고 주장할 수 있는 예제들이다.

 (예제 3.2)  

그림 5 의 그래프는 해밀턴 사이클을 포함하고 있지 않다.

그림 5  해밀턴 사이클이 업슨 그래프

5 개의 정점이 존재하므로, 해밀턴 사이클은 5 개 간선을 가져야 한다. 해밀턴 사이클이 있는 그래프에서 간선들을 제거할 수 있다고 가정하자. 해밀턴 사이클 안의 각 정점이 차수가 2 이므로, 에 부속된 하나의 간선과 에 부속된 간선을 제거한다. 그러나 이것은 네 개의 간선들만 남는다 - 이는 길이가 5 인 해밀턴 사이클에 대해서는 충분하지 않다. 따라서 그림 5 의 그래프는 해밀턴 사이클을 포함하고 있지 않다.

예제 2 에서 그래프에 해밀턴 사이클이 없다는 것을 보일 때와 같이, 제거되는 간선들을 한 번 이상 세지 않도록 세심한 주의를 하여야 한다. 예제 2 (그림 5 참조) 에서 에 부속된 하나의 간선과 에 부속된 간선을 제거한다면, 이 간선들은 다르다. 그러므로 그림 5 의 그래프로부터 사이클을 생성하기 위해 두 개의 간선을 제거해야만 하는 추론은 옳은 것이다.

두 번씩 세는 예로, 그림 5 의 그래프가 해밀턴 사이클을 가지고 있지 않다는 것을 보이기 위해서 전개하는 잘못된 주장을 고려해 보자. 5 개의 정점이 있으므로, 하나의 해밀턴 사이클은 5 개의 간선을 가져야 한다. 해밀턴 사이클을 생성하기 위해 그래프에서 간선을 제거할 수 있다고 가정하자. c 에 부속된 두 개의 간선과 a, b, d, e 에 부속된 하나의 간선을 제거한다. 이로써 두 개의 간선이 남는데 - 해밀턴 사이클로는 충분치 못하다. 따라서 그림 6 의 그래프는 해밀턴 사이클을 포함하고 있지 않다. 이 주장에서 잘못된 점은 c 에 부속된 두 개의 간선을 제거한다면 a, b, d, e 에 부속된 간선들도 두 개를 제거한다고 하는 것이다. 두 개의 정점에 부속된 두 개의 제거된 간선을 세지 말아야 한다. 그림 6 의 그래프는 해밀턴 사이클을 가지고 있음에 유의하자.

그림 6  해밀턴 사이클을 가지는 그래프

 (예제 3.3)  

그림 7 의 그래프 G 가 해밀턴 사이클을 포함하지 않음을 보이자.

그림 7  해밀턴 사이클이 없는 그래프

G 가 해밀턴 사이클 H 을 가진다고 하자. 간선 (a, b), (a, g), (b, c), (c, k) 는 해밀턴 사이클 안의 각 정점이 차수가 2 를 가지므로 H 안에 있다. 따라서, 간선 (b, d) 와 (b, f) 는 H 안에 있지 않다. 그러므로 간선 (g, d), (d, e), (e, f), (f, k) 는 H 안에 있다. H 안에 있는 것으로 알려진 간선들은 사이클 C 를 형성한다. C 에 부가적인 간선을 첨가하는 것은 H 안에 있는 차수가 2 보다 큰 어떤 정점을 주게 될 것이다. 이 모순은 G 가 해밀턴 사이클을 가지지 않는다는 것을 보여 준다.

판매원 방문 문제 (traveling salesperson problem) 는 그래프에서 해밀턴 사이클을 찾는 문제와 관련이 있다 (서론에서 판매원 방문 문제의 변형으로 간단히 언급한 바 있다). 이 문제는 주어진 가중치 그래프 G 가 주어지면, G 안에서 최소 길이를 가지는 해밀턴 사이클을 찾는 문제이다. 가중치 그래프에서 도시를 정점으로 거리를 간선으로 생각한다면, 판매원 방문 문제는 판매원이 어느 도시를 출발항 각 도시를 한 번만 방문하여 출발지로 돌아오는 최소의 경로를 찾는 문제이다.

 (예제 3.4)  

그림 8 의 그래프 G 사이클 C = (a, b, c, d, a) 는 해밀턴 사이클이다. C 의 어떤 간선을 11 이 부여된 간선으로 대체하여도 C 의 길이는 증가할 것이다 ; 따라서 C 은 G 에 대하여 최소 길이 해밀턴 사이클이다. 그러므로 C 는 G 에 대하여 판매원 방문 문제를 해결한다.

그림 8  판매원 방문 문제를 위한 그래프

오일러 사이클을 찾는 알고리즘들이 있으나 ([Even, 1979] 을 보라), 만약 개의 간선을 가지는 그래프에 대해 시간이 소요되는 알고리즘이 존재한다면, 해밀턴 사이클을 찾기 위한 방법으로 알려진 모든 알고리즘들이 최악의 경우 지수 또는 팩토리얼 시간을 요구한다. 그렇기 때문에 최소에 근접한 길이를 가지는 사이클을 찾는 방법이 판매원 방문 문제를 해결하기 위하여 종종 사용된다. 해밀턴 사이클 문제 (혹은 판매원 방문 문제) 를 다항 시간 (polynomial-time) 에 해결하는 알고리즘을 제시하거나, 이 문제들이 다항 시간 내에 해결되지 않는다는 것을 증명하는 사람은 순식간에 명성을 얻게 될 것이다.

-큐브 안의 해밀턴 사이클을 고찰하면서 이 절을 마무리하고자 한다.

 (예제 3.5)   -큐브안의 그레이 코드와 해밀턴 사이클

병렬 계산을 위한 링 모델 (ring model) 을 고려해 보자. 이를 그래프로 표현하면 단순 사이클이 된다 (그림 9 를 보라). 정점들은 프로세서들로 나타낸다. 프로세서 와 사이의 간선은 서로가 통신할 수 있다는 것을 의미한다. 각 프로세서가 다른 두 개의 프로세서와 직접 통신할 수 있다는 것을 알 수 있다. 인접하지 않은 프로세서들은 메시지를 보내 통신할 수 있다.

그림 9  병렬 계산을 위한 링 모델

-큐브 (예제 7 를 보라) 는 병렬 계산을 위한 다른 모델이다. -큐브는 프로세서들 간에 더 많은 연결 차수를 갖는다. -큐브는가 개의 프로세서로 링 모델을 시뮬레이션할 수 있을 때의 문제를 고려해 보자. 그래프 용어에서, -큐브가 부분 그래프로서 개의 프로세서를 가지고 있기 때문에, -큐브가 해밀턴 사이클을 언제 포함하는지를 알고 싶어한다 [-큐브가 임의의 프로세서들을 가진 링 모델을 시뮬레이션할 수 있을 때의 문제는 연습 문제에 남겨두었다 (연습 문제 18 을 보라)].

-큐브가 해밀턴 사이클을 포함한다면 1-큐브가 사이클을 전혀 가지지 않기 때문에 는 2 보다 커야 한다는 것을 먼저 알 수 있다.

먼저 언급했던 (예제 7 를 보라), -큐브의 정점들을 0, 1, 2, ..., 과 같이 번호를 붙이던 것을 상기하자. 이때 하나의 간선은 두 개의 정점을 연겨ㅓㄹ하며, 이를 위한 필요 충분 조건은 그 번호의 이진 표현은 인접한 정점과 연결하며, 이를 위한 필요 충분 조건은 그 번호의 이진 표현은 인접한 정점과 비교할 때 단 하나의 비트만 다르다. 따라서 -큐브가 해밀턴 사이클을 가질 필요충분조건은 이고, 다음과 같은 수열이 존재한다.

                                                 (1)

이때 각 은 -비트 스트링이고 다음을 만족해야 한다 :

• 모든 -비트 스트링은 수열의 어딘가에 나타난다.
• 와 는 한 비트가 다르다.
• 과 은 한 비트만 다르다.

수열 (1) 은 그레이 코드 (Gray code) 라 한다. 일 때 그레이 코드 (1) 은 다음의 해밀턴 사이클에 대응된다.



(이때, 모든 정점들은 포함되고 간선 (), , 은 (, ) 은 서로 다르다. 일 때, 그레이 코드 0, 1 은 경로 (0, 1, 1) 에 대응된다. 이는 모서리 선 (0, 1) 이 반복된 것이므로 사이클이 아니다.

그레이 코드는 다른 분야에서 다양하게 연구되어 왔다. 예를 들어, 그레이 코드는 아날로그 정보를 디지털 형태로 바꾸는데 사용되어 왔다 ([Deo] 를 보라). 모든 양의 정수 에 대해 그레이 코드를 어떻게 구축하는지를 살펴보자. 그래서 -큐브가 2 보다 큰 모든 양의 정수 에 대해 해밀턴 사이클을 갖는다는 것을 증명하자.

 (정리 3.5)  

을 수열 0, 1 로 표시하자. 를 다음의 규칙으로   를 사용하여 정의한다.

(a) 은 수열 를 거꾸로 표기한 것이다.

(b) 은 수열 의 앞부분에 0 을 첨가한 수열이다.

(c) 은 수열 의 앞부분에 1 을 첨가한 수열이다.

(d) 은 과 로 이루어진 수열이다.

따라서 은 모든 양의 정수 에 대해 그레이 코드이다.

증명   에 대한 귀납법으로 정리를 증명한다.

기본 단계   수열 0, 1 이 그레이 코드이기 때문에, 정리는 이 1 일 때 참이다.

귀납 단계   이 그레이 코드라고 가정하자. 안의 각 스트링은 0 으로 시작하고, 연속적인 스트링들간의 어떤 차이는 안의 대응되는 스트링의 다른 비트에서 얻을 수 있다. 그러나 이 그레이 코드이므로 의 스트링의 연속적인 쌍은 정확하게 한 비트가 다르다.

의 마지막 스트링을 라 하고, 의 첫 스트링을 라 하자. 로부터 첫 번째 비트를 지우고 로부터 첫 번째 비트를 지우면, 남은 스트링은 서로 같다. 안의 첫 번째 비트가 0 이고 의 첫 번째 비트가 1 이기 때문에, 안의 마지막 스트링과 의 첫 스트링은 한 비트만 다르다. 마찬가지로, 안의 첫 스트링과 안의 마지막 스트링은 한 비트만 다르다. 따라서 은 그레이 코드이다.

 (따름 정리 3.7)  

-큐브는 인 모든 양의 정수 에 대하여 해밀턴 사이클을 가진다.

 (예제 3.8)  

정리 6 을 이용하여 으로 시작하는 그레이 코드 을 구축해 보자.

이 절을 200년 전의 문제 하나를 보기로 보면서 마치도록 하자.

 (예제 3.9)   기사 순회 문제

체스 게임에서 기사 수직 또는 수평으로 2 칸 그리고 그외 수직되게 1 칸을 움직이게 되어 있다. 예를 들어, 그림 10 에서 K 라고 표시된 사각형의 기사는 X 라고 표시된 어떤 곳으로도 움직일 수 있다. 체스판의 기사의 행로 (knight's tour of an  board) 는 한 사각형에서 시작하고, 규칙에 따라 정해진 각 사각형을 방문하고, 최초의 위치로 돌아온다. 이 문제는 존재하는 기사 순회 중에서 을 결정하는 문제이다.

그림 10  체스에서 기사의 바른 움직임

그래프를 이용하여 이 문제를 모델화할 수 있다. 판의 사각형을 번갈아가며 흰색과 검은색으로 칠해 보자. 각 정점을 판의 색깔로 대체하고, 정당한 움직임이 허용되는 정점 간에 간선을 허용한다 (그림 11 을 보라). 이 그래프를 이라 표기한다. 그런데  판 위에 기사의 순회가 존재할 필요 충분 조건은 이 해밀턴 사이클을 가진다.

그림 11 4×4 체스판과 그래프

이 해밀턴 사이클을 가지면 이 짝수임을 보인다. 이를 보이기 위해, 이 이분 그래프임에 주의하자. 정점들을 흰색 사각형에 해당되는 정점의 집합 과 검은색 사각형에 해당되는 정점의 집합 로 나눌 수 있다 ; 각각의 간선은 과 에 부속된다. 어떤 사이클이든 정점이 과 를 번갈아 가며 나타나야 하기 때문에, 안의 어떤 사이클도 짝수의 길이를 가져야 한다. 그러나 하나의 해밀턴 사이클은 각 정점을 한 번씩 방문해야 하기 때문에, 안의 해밀턴 사이클은 의 길이를 가져야 한다. 따라서 은 '짝수여야 한다.

앞선 결과를 고려하여, 기사 순회가 이루어질 수 있는 가장 작은 판은 2×2 이다, 그러나 그것은 기사가 정당한 움직임이 허용되지 않기 때문에 기사 순회가 이루어지지 않는다. 기사 순회를 고려할 수 있는 그 다음 작은 판은 4×4 판인데, 그것 역시 기사 순회를 갖지 못한다. 가 해밀턴 사이클을 가지지 못하는 것을 보이기 위해 모순법을 이용해 보인다.

가 해밀턴 사이클 을 가진다고 하자. 은 왼쪽 위 사각형에 대응된다고 가정하자. 윗쪽과 아랫쪽의 8 개의 사각형을 바깥쪽 사각형 (outside squares) 이라 하고 나머지 안쪽의 8개를 안쪽 사각형 (inside squares) 이라 하자. 기사는 안쪽 사각형에서 바깥쪽 사각형에 도착해야 하고 또한 바깥쪽 사각형에서 안쪽 사각형으로 움직여야 한다. 따라서 사이클 C 안에서 각 바깥쪽 사각형에 해당하는 정점은 먼저 와야하고, 안쪽 사각형에 대응되는 정점들이 뒤에 와야 한다. 그러나 기사가 만드는 움직임을 보면, 가 홀수인 정점  는 흰 사각형에 대응되고, 짝수 인 정점 에 대응되는 것은 검은색 사각형임을 알 수 있다. 따라서 바깥쪽 사각형만을 방문하는 것은 흰색이고 안쪽을 방문하는 것은 검은색이다. 그러므로 C 는 해밀턴 사이클이 아니다. 이 모순은 가 해밀턴 사이클을 가지지 않음을 증명한다. 이러한 주장은 Louis Posa 에 의해 제기됐는데, 그때 그는 십대였다.

그래프 해밀턴 사이클을 갖는다. 이 사실은 간단하게 증명할 수 있다. 인 모든 짝수 에 대해 이 해밀턴 사이클을 가지는 것은 가장 기본적인 방법을 이용하여 보여줄 수 있다 ([Schwenk] 을 보라). 이 증명은 더 작은 판에 대해 해밀턴 사이클을 명시적으로 구축할 수 있음을 보이고, 이 작은 판을 좀 더 큰 판에 대해 확장하여 해밀턴 사이클을 얻을 수 있음을 보인다.