구독상품안내
가운데층 문제는 특정 그래프에 ‘해밀턴 회로’가 반드시 있는지 보이는 것입니다. ‘해밀턴 회로’에 대해 말하기 앞서 ‘오일러 회로’부터 이야기할까합니다.
대표적인 오일러 회로 문제로 스위스의 수학자 레온하르트 오일러가 소개하고 풀어서 유명한 쾨니히스베르크의 다리 문제를 들곤 합니다. 쾨니히스베르크(지금은 러시아의 칼리닌그라드)라는 도시에 있는 7개의 다리를 한 번씩만 지나 원래 자리로 되돌아올 수 있는지 묻는 문제지요. 오일러는 1736년 이 문제의 답이 없다고 밝혔습니다.
오일러 회로란 어떤 그래프에서 모든 선을 한 번씩만 지나고 원래 자리로 돌아오는 방법을 말합니다. 오일러 회로가 반드시 있으려면 각 꼭짓점에 연결된 선의 수가 홀수인 꼭짓점, 즉 홀수점이 없어야 한다는 것이 익히 알려져 있습니다.
해밀턴 회로의 시작은 게임
1857년 아일랜드 출신의 수학자 해밀턴 경은 둘이서 즐길 수 있는 재미있는 게임을 개발했습니다. ‘이코시안 게임’으로 불리는 이 게임은 정십이면체 위에 있는 꼭짓점 20개를 딱 한 번씩만 지나 출발점으로 되돌아오는 길을 찾는 겁니다. 게임의 방법은 간단합니다.
첫 번째로 말을 움직이는 사람은 상대를 방해하기 위해 정십이면체의 변을 따라 총 5번 말을 움직입니다. 두 번째 사람은 그 상태에서 이어받아 말을 움직여서 꼭짓점을 한 번씩만 지나 출발점으로 되돌아오면 됩니다. 만약 성공한다면 두 번째 사람이 이기고, 그렇지 못하면 첫 번째 사람이 이깁니다.
해밀턴 경은 런던의 장난감 제작자인 존 자크에게 25파운드를 받고 이 게임의 권리를 팔았고, 19세기 후반에 이르러 이코시안 게임은 보드게임으로 만들어져 유럽 곳곳에서 팔렸습니다. 이후 수학자들은 그래프에서 모든 꼭짓점을 한 번씩 지나 시작점으로 돌아오는 경로를 해밀턴 경의 이름을 따서 해밀턴 회로라고 불렀습니다.
그런데 해밀턴 회로가 있는지 없는지 묻는 문제는 매우 어렵습니다. 오일러 회로처럼 간단하지 않은 거지요. 실제로 해밀턴 회로가 있는지 알아보는 문제는 ‘NP-완전’이라는 것이 이미 밝혀져 있습니다. 만일 어떤 그래프에 해밀턴 회로가 있는지 알아내는 매우 효율적인 알고리듬이 만들어지면 ‘P=NP’라는 수학계의 7대 난제 중 하나가 해결되는 셈입니다. 많은 수학자가 ‘P≠NP’라고 믿고 있어서 아마도 해밀턴 회로를 효율적으로 찾는 알고 리듬은 없다고 예상합니다.
이제 본격적으로 ‘가운데층 문제’에 대해 알아봅시다. 먼저 가장 간단한 경우부터 생각해 봅시다. 여기 꼭짓점 6개가 있습니다. 각각의 이름은 001, 010, 100처럼 1이 하나고 0이 두 개인 문자열이거나 011, 101, 110처럼 1이 두 개고 0이 하나인 문자열입니다. 만일 어떤 꼭짓점 A의 이름에 적힌 세 숫자 중 하나를 골라 0은 1로, 1은 0으로 바꿔서 다른 꼭짓점 B의 이름이 나오면 두 꼭짓점 사이에 선을 그어 그래프를 만들어 봅시다. 이렇게 만든 그래프에 해밀턴 회로가 있을까요?
이렇게 만든 가운데층 그래프 모두에 해밀턴 회로가 있는지 증명하는 문제가 가운데층 문제입니다. 가운데층이라고 부르는 이유는 0과 1로 이뤄진 2n+1개인 문자열 중에 0과 1의 개수가 각각 문자열 길이의 절반에 가깝기 때문입니다.
가운데층 문제를 처음 제기한 사람에 대해선 의견이 분분합니다. 1983년 체코의 컴퓨터과학자 이반 하벨이 쓴 논문이 처음이라는 설도 있고, 1984년 미국 수학자 마셜 벅과 더그 위드만의 논문이 시초라는 이야기도 있습니다.
한편 1988년 미국 수학자 할 키얼스태드와 윌리엄 트로터가 쓴 논문에 따르면 수학자들은 이 문제를 출제한 장본인으로 서로 다른 사람을 지목했습니다. 헝가리의 수학자 에르되시 팔은 트로터를, 트로터는 아르헨티나 출신 수학자 이탈로 호세 데테르를, 데테르는 에르되시가 가운데층 문제를 만든 사람이라고 주장했습니다. 하지만 데테르는 얼마 뒤 말을 바꿔서 하벨이 1983년에 쓴 논문에서 처음 제기했다고 이야기했습니다.
가운데층 문제를 해결하기까지
n이 1일 때는 해밀턴 회로가 있다는 것을 쉽게 보일 수 있습니다. 하지만 n이 2만 되도 해밀턴 회로를 찾기가 쉽지 않습니다. 하지만 n이 19 이하일 때 해밀턴 회로가 반드시 있다는 것은 컴퓨터를 통해 밝혔습니다.
일반적인 n에 대해서는 어떨까요? 1995년 트로터와 독일의 수학자 스테판 펠스너는 n이 크다면 어느 꼭짓점도 두 번 들르지 않고 25% 이상의 꼭짓점을 방문한 뒤 시작점으로 되돌아올 수 있다고 증명했습니다. 같은 해 미국 수학자 칼라 새비지와 피터 윙클러는 25%를 83%로 높였습니다.
2004년 로버트 존슨은 어떤 상수 c에 대해 전체 꼭짓점 중에
그리고 올해 3월 토르슈텐 뮈체는 모든 n에 대해 가운데층 그래프에는 해밀턴 회로가 있다는 것을 증명했습니다. 뿐만 아니라 각 n에 대해 가운데층 그래프의 해밀턴 회로 수는 무려
까다로운 해밀턴 회로 문제
가운데층 문제는 헝가리 출신 수학자 로바스 라슬로가 1969년 캐나다 캘거리에서 열린 국제학회에서 제기한 ‘로바스의 추측’의 특수한 경우입니다. 로바스는 조합론 분야에서 매우 잘 알려진 대가로, 이 문제를 제시할 당시 21살에 불과했습니다.
로바스는 우리나라와도 인연이 깊어서 2014년에 열린 세계수학자대회를 유치할 당시인 2009년 국제수학자연맹의 회장으로, 우리나라를 여러 번 방문했습니다. 지금은 헝가리의 과학자를 대표하는 정부 기관인 헝가리 과학 아카데미의 총장입니다.
1969년 로바스는 아무렇게나 연결된 그래프에 대칭성이 많다면 5개의 그래프를 빼고는 해밀턴 회로가 있다고 추측했습니다. 여기서 대칭성이 많다는 것은 어느 두 꼭짓점 A, B를 잡아도 전체 그래프의 성질중 하나인 어떤 대칭이 A를 B로 바꿔준다는 것입니다. 가운데층 그래프는 대칭성이 매우 많기 때문에 로바스의 추측이 옳다면 가운데층 문제도 맞게 됩니다.
하지만 로바스의 추측은 40년이 지난 지금도 미해결 문제입니다. 이것으로 봤을 때 해밀턴 회로에 대한 문제는 다루기가 무척 까다롭습니다. 그래도 가운데층 문제가 풀린 것처럼 로바스의 추측도 머지않아 풀리지 않을까요?
