안녕하세요 유홍석수학연구소 조교입니다.
오늘 알뜰신수에서는 한붓그리기 문제의 수학적 접근에 대해 알려드리겠습니다.
18세기 무렵 유럽에 쾨니히스베르크라는 도시가 있었는데, 그 도시를 가로 질러서 큰 강이 하나 흐르고 있었는데, 모두 7개의 다리가 강 위에 놓여 있었다. 어느 날 이 도시의 시민 하나가 “한 다리를 두 번 건너지 않고, 단 한 번씩으로 7개의 다리를 모두 건널 수 있을까?” 라는 문제를 내었다. 재미있는 문제라고 생각한 사람들은 그 방법을 알면 외지인의 관광 안내에도 도움이 될 거라고 생각하여 앞 다투어 풀이에 도전하였으나, 어찌된 일인지 제대로 풀었다는 사람은 한 명도 나타나지 않았다. 그러는 동안에 이 문제는 널리 소문이 나서, 독일 전역에서도 아주 유명한 문제가 되기에 이르렀다.
그런데 오일러는 1736년에 이 문제의 답이 없다는 것을 발견하였습니다. 오일러는 다리를 길거나 짧은 선으로 생각하고, 다리를 건너지 않고 걸어 다닐 수 있는 땅을 줄여서 점으로 생각하여 이 강과 다리를 다음과 같은 그림으로 나타내었습니다.
그리고, 이 그림이 연필을 떼지 않고 선을 한 번씩만 지나게 그릴 수 있는가 하는 한붓 그리기 문제로 바꿔서 생각하였습니다. 여기서 위상수학이 태어난 것이며, 한붓 그리기가 위상수학의 한 소재가 된 것입니다.
그러면 왜 위의 그림이 한붓 그리기가 불가능한지 알아보겠습니다. 먼저, 한 점에 모이는 선이 짝수 개인 점을 ‘짝수점’, 그 점에 모이는 선이 홀수 개인 점을 ‘홀수점’이라고 합시다. 다음 그림에서 ⑴은 짝수점만 가지고 있으며, ⑵는 홀수점을 2개, ⑶은 홀수점을 4개 가지고 있습니다. 각자 그려보면 알겠지만 짝수점만 있으면 어느 점에서 시작하여도 한붓 그리기가 가능합니다. 그러나 홀수점이 2개 있으면 반드시 홀수점에서 시작하여야 한붓 그리기가 가능하며, 홀수점이 4개 이상 있으면 한붓 그리기가 불가능합니다.
쾨니히스베르그의 다리 문제는 홀수점이 4개 있는 문제이므로 한붓 그리기가 불가능한 문제가 됩니다. 오일러가 이 문제를 해결한 후 139년이 지난 1875년에 8번째 다리가 놓여서, 같은 다리를 두 번 이상 건너지 않고 모든 다리를 산책할 수 있게 되었다고 합니다. 어디에 다리를 놓으면 되는지 그리고 그 때 어떤 순서로 다리를 건너면 되는지 여러분도 직접 한번 생각해 보는 것도 좋을 것 같습니다.
오일러의 한붓그리기 정리
정리 1. 명제 ‘연결되어 있는 그래프 G가 시작점과 종착점이 같은 오일러 경로(한붓그리기로 닫혀 있는 경로)이다.’의 필요충분조건은 ‘G 의 모든 꼭짓점의 차수가 짝수이다'.
다리를 산책하는 평범한 일상에서 이렇게 새롭고 신기한 수학이 만들어지는 게 신기하지 않나요?
지금까지 오일러와 함께한 알뜰신수 시간이었습니다!
다음 시간에 만나요
