쾨니히스베르크의 일곱 다리와 한붓그리기의 수학

18세기 프로이센의 도시 쾨니히스베르크에는 강 가운데 섬 두 개와 양쪽 강변을 잇는 다리가 일곱 개 있었다. 모든 다리를 꼭 한 번씩만 건너 산책을 마칠 수 있느냐는 질문에, 1736년 레온하르트 오일러는 그런 길은 없다고 증명했다. 오일러는 땅의 모양과 다리의 길이를 모두 지우고, 어느 땅이 어느 땅과 몇 개의 다리로 이어지는지만 남겼다. 이 생각이 오늘날 그래프 이론의 출발점이다.

지도를 지우고 연결만 남긴다

오일러는 강으로 나뉜 네 덩어리의 땅을 각각 점 하나로, 다리를 점과 점을 잇는 선으로 바꾸었다. 그러면 산책 문제는 네 개의 점과 일곱 개의 선으로 된 그림을 연필을 떼지 않고, 같은 선을 두 번 지나지 않으면서 모두 그릴 수 있느냐는 문제가 된다. 흔히 한붓그리기라고 부르는 문제다.

이 변환이 중요한 이유는 답에 영향을 주지 않는 정보를 모두 버렸기 때문이다. 다리가 얼마나 긴지, 섬이 얼마나 큰지, 강이 어느 쪽으로 흐르는지는 질문과 상관이 없다. 남는 것은 무엇이 무엇과 이어져 있는가라는 관계뿐이다. 길이와 넓이를 다루던 당시의 기하학과 달리, 연결 방식 자체를 대상으로 삼는 수학이 여기서 시작되었다.

들어간 만큼 나와야 한다

오일러의 논리는 단순하다. 산책 도중 어떤 땅을 지나가려면 다리 하나로 들어가서 다른 다리 하나로 나와야 한다. 그러므로 출발점과 도착점이 아닌 땅에는 다리가 짝수 개 붙어 있어야 한다. 한 점에 붙은 선의 수를 그 점의 차수라고 하면, 중간에 지나가는 점의 차수는 모두 짝수여야 한다.

홀수 차수가 허락되는 점은 산책을 시작하는 점과 끝내는 점뿐이다. 따라서 한붓그리기가 가능하려면 차수가 홀수인 점이 하나도 없거나 정확히 두 개여야 한다. 홀수 차수인 점이 없으면 출발한 곳으로 돌아오는 산책이 되고, 두 개이면 그 두 점 가운데 하나에서 출발해 다른 하나에서 끝난다. 쾨니히스베르크에서는 네 땅의 차수가 각각 5, 3, 3, 3으로 모두 홀수였다. 홀수 점이 네 개이므로 원하는 산책은 불가능하다.

홀수 차수인 점의 수	한붓그리기	경로의 모양
0개	가능	출발점으로 돌아옴
2개	가능	두 홀수 점이 시작과 끝
4개 이상	불가능	같은 선을 다시 지나야 함

조건이 충분하다는 증명

오일러는 홀수 점이 둘보다 많으면 불가능하다는 것을 분명히 보였다. 반대로 조건을 만족하면 언제나 한붓그리기가 가능하다는 것은 그가 언급은 했지만 엄밀히 증명하지는 않았다. 이 방향의 증명은 1873년 독일의 칼 히어홀처가 발표했다. 그의 방법은 아무 점에서나 출발해 막힐 때까지 걷고, 아직 지나지 않은 선이 남은 점에서 다시 작은 고리를 만들어 끼워 넣는 일을 되풀이하는 것이다. 이 방법은 지금도 컴퓨터로 한붓그리기 경로를 찾을 때 쓰인다.

눈 치우는 차의 경로

오일러의 질문은 오늘날 도시 행정의 문제로 이어진다. 제설차, 쓰레기 수거차, 우편 배달원은 정해진 구역의 모든 도로를 빠짐없이 지나가야 한다. 같은 길을 두 번 지나면 시간과 연료가 낭비되므로, 이들의 경로를 짜는 일은 한붓그리기 문제와 같다. 도로망에 홀수 교차로가 있으면 어떤 길은 반드시 다시 지나야 하는데, 다시 지나는 길의 총길이를 가장 짧게 고르는 문제를 중국 우편배달부 문제라고 부른다. 1962년 중국의 수학자 관메이구가 이 문제를 제시해 그런 이름이 붙었다.

점이 아니라 선을 빠짐없이 지나는 문제는 이렇게 효율적으로 풀리는 방법이 알려져 있다. 흥미롭게도 모든 점을 한 번씩만 지나는 문제는 훨씬 어렵다. 모든 도시를 한 번씩 들르는 경로를 찾는 문제는 지금도 큰 규모에서 빠르게 푸는 방법이 알려지지 않은 대표적인 난제다. 선과 점 하나 차이로 문제의 성격이 완전히 바뀐다.

남은 질문

쾨니히스베르크는 지금 러시아의 칼리닌그라드가 되었고, 제2차 세계대전과 그 뒤의 재건을 거치며 다리의 수와 위치가 바뀌었다. 바뀐 다리로 오일러의 질문을 다시 풀어 보는 일은 수학 애호가들의 놀이가 되었다. 정작 수학에서 남은 질문은 다른 곳에 있다. 오일러처럼 문제의 본질만 남기고 나머지를 지우는 추상화가 언제 성공하고 언제 중요한 정보를 잃는지 판단하는 일은, 공식으로 정리되지 않은 수학자의 감각으로 남아 있다.