3-regular graph의 세계일주

도시들이 주어져 있고, 각각의 도시에 대해 정확히 세 개의 서로 다른 도시로 갈 수 있는 비행기편이 있다고 한다. 어떤 사람이 이 편로들을 이용해 이 사람의 고향에서 출발해 모든 도시들을 한 번씩만 거쳐 다시 원래 도시로 돌아왔다면 이 루트를 세계 일주라 부른다. 만약 이 도시들에서 세계 일주가 가능했다면, 그 여정과 다른 방법으로 세계 일주가 가능하다. (단, 기존 세계 일주의 여정을 거꾸로 여행하는 것은 제외한다.)

2001년 일본 수학 올림피아드에서 등장했던 문제. 실은 1946년 Cedric Smith가 증명한 것이 그 시초라고 한다. 정리하면, 모든 점의 차수가 3인 그래프 (3-regular graph)에 해밀턴 회로가 존재한다면 반드시 또 다른 해밀턴 회로가 존재한다는 내용이다.

먼저 이미 존재하는 해밀턴 회로에 포함되는 한 변 uv를 고정한다. 그리고 이 변을 지나고 u에서 시작하는 모든 해밀턴 경로(회로가 아닌 path)들을 편의상 “좋은 경로”라고 부르도록 한다. 어떤 좋은 경로 Pw에서 끝난다고 할 때, w가 (1) u도 아니고 (2) P 위의 w 직전의 점도 아닌 어느 한 점 x와 변으로 연결되어 있다면, u에서 시작해 P를 따라 x까지 간 후, x에서 w로 이동하여 다시 원래 경로의 역순으로 쭉 따라간 경로 역시 좋은 경로가 된다. 이렇게 한 좋은 경로 P에서 변 wx를 이용해 다른 좋은 경로 Q를 얻어낼 수 있다면, 역으로 Q에서도 마찬가지로 변 wx를 이용해 P를 얻을 수 있다.

여기서, 한 그래프 G를 다음과 같이 잡는다. G의 점은 “좋은 경로”들에 해당하고, 만약 한 좋은 경로에서 앞서 설명한 바와 같은 방법으로 다른 좋은 경로를 만들 수 있다면 이 두 좋은 경로에 해당하는 두 점을 변으로 연결한다. (역으로 만드는 것도 가능하므로 방향성 없는 변(undirected edge)으로 그려도 괜찮다) 그러면, u에서 시작해 w로 끝나는 좋은 경로 $latex P4에 대해서

  • 만약 uw가 변으로 연결되어 있었다면, PG에서의 차수는 1이 되고, (앞서 w와 인접한 x를 찾을 때 총 차수 3에서 (1), (2)에 해당하는 두 경우를 제외하게 됨)
  • 그렇지 않다면 P의 차수는 2가 된다.

그런데 전자의 경우가 바로 변 uv를 지나는 모든 해밀턴 회로에 해당되며, 일대일대응이 된다. 따라서 그래프 G는 좋은 경로들을 꼭지점으로 생각하는 차수가 1 또는 2인 그래프인데, 차수가 1임이 곧 uv를 포함하는 해밀턴 회로임과 동치인 것이 된다. 차수가 1인 점, 즉 해밀턴 회로는 존재한다고 문제에서 주어졌고, 그래프에서 차수의 합은 짝수이기 때문에 반드시 또 다른 차수가 1인 점(=해밀턴 회로)가 존재하게 되어 증명이 끝난다.

그래프들을 점으로 보는 그래프를 생각하는 재미있는 발상이 인상적이었다. 똑같은 방법을 직접적으로 응용하면 조금 더 일반화된 결과를 얻을 수 있는데, d가 홀수일 때 d-regular 그래프의 임의의 한 변에 대해 그 변을 지나는 해밀턴 회로의 개수가 짝수라는 것.[1] 또한 원래 문제와 동일한 조건에서 해밀턴 회로의 개수는 3개 이상이 됨도 비교적 쉽게 증명할 수 있게 된다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/07/03)

References

[1] W. T. Tutte, “On Hamiltonian Circuits” Journal of the London Mathematical Society, Volume s1-21, Issue 2, 1 April 1946, Pages 98–101. DOI: 10.1112/jlms/s1-21.2.98

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중