쾨니히스베르크의 다리와 일필휘지(一筆揮之)

 

프로이센의 소도시 쾨니히스베르크(Königsberg)는 철학자 칸트가 평생을 지낸 도시로 유명하다. 칸트는 매일 같은 시간에 산책을 하여 사람들이 그가 산책하는 것을 보고 시계를 맞추었다는 일화가 전해 오는 곳이다. 이 도시는 수학과 관련해서도 기념비적인 곳이다.

 

쾨니히스베르크 도시를 관통하는 프레겔 강에는 2개의 섬이 있고 이들 섬과 육지는 7개의 다리로 연결되어 있다. 당시 사람들은 '같은 다리를 두 번 건너지 않고, 모든 다리를 건널 수 있을까?'하는 문제를 생각했는데 이를 '쾨니히스베르크의 다리 문제'라고 한다. 쾨니히스베르크의 다리 문제는 연필을 떼지 않고 한 번에 그리는 한붓그리기, 곧 '일필휘지(一筆揮之)'가 가능한가의 문제라고도 할 수 있다.

쾨니히스베르크의 다리 문제를 해결하기 위해 여러 가지 시도를 해 보면 알겠지만 같은 다리를 두 번 건너지 않고 모든 다리를 건너는 것은 불가능하다.

 

1736년 오일러(Euler, L. ; 1707~1783)는 중복되지 않게 7개의 다리를 건너는 것이 불가능함을 수학적으로 증명했다. 문제를 해결하기 위해 다음과 같이 다리와 육지의 연결 상태를 그래프로 표현하면 편리하다.

오일러는 어떤 그래프가 한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한 번씩만 지나서 처음 출발점으로 되돌아올 수 있으려면 그래프의 각 꼭짓점에 연결된 변의 개수가 모두 짝수이어야 함을 증명하였다.

 

위의 그래프에서 홀수점의 개수가 4개이므로, 오일러 경로를 갖지 않는다. 따라서 쾨니히스베르크의 다리에 관한 문제는 해가 존재하지 않는다는 것이 밝혀졌다.