본문 바로가기
정신체조수학

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

by mathpark 2012. 11. 3.

 

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

 

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

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

 

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


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

 

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

 

 

728x90

'정신체조수학' 카테고리의 다른 글

아주 큰 소수를 찾아라  (4) 2012.11.13
체스에 얽힌 등비수열  (0) 2012.11.08
자동차의 경제속도는?  (0) 2012.11.02
진자의 등시성  (0) 2012.11.02

댓글