메인메뉴 바로가기
본문바로가기

과학이야기 재미있고 다양한 과학이야기를 읽어보세요

모든 다리를 한 번씩만 건너서 산책하라!
조회 334 2021.05.24 신고

쾨니히스베르크의 다리 건너기


‘쾨니히스베르크(Königsberg)’는 현재 러시아에 있는 칼리닌그라드라는 도시로 예전에는 독일 땅이었다. 그곳에는 ‘프레겔’이라는 강이 흐르고 있고, 강을 가로지르는 7개의 다리가 놓여 있었다. 


by Bogdan Giu?c? [CC BY-SA 3.0 Wikimedia Commons] 

 

 


마을 사람들은 “강을 가로지르는 7개의 다리 중 같은 다리를 두 번 건너지 않고, 모든 다리를 각각 한 번씩만 건너서 산책을 할 수 있을까?”에 대해서 궁금해했고, 많은 사람들이 이 문제를 풀려고 노력했지만 해결하지 못했다. 당시 유명한 수학자인 오일러는 다리를 직접 건너는 대신 아래와 같이 그림을 그려 점과 선으로 이루어진 ‘한붓그리기’ 문제로 간단하게 정리하고 이를 해결했다.



여기서 ‘한붓그리기’ 원칙은 연필을 떼지 않은 채로 같은 선을 두 번 지나지 않고 한 번에 그리는 것을 말한다. 오일러는 짝수점과 홀수점이라는 것을 이용해서 한붓그리기가 가능한지를 찾아냈다. 짝수점이란 선이 짝수 개 연결된 점이고, 홀수점이란 선이 홀수 개 연결된 점이다.


아래 4가지 그림의 짝수점과 홀수점은 다음과 같다.




(1)과 같이 홀수점이 없고 모두 짝수점일 경우 출발점과 도착점이 같도록 한붓그리기를 할 수 있다. (2), (4)와 같이 홀수점이 2개일 경우는 한 홀수점에서 출발하여 다른 홀수점에서 끝나도록 한붓그리기를 할 수 있다. 그러나 (3)과 같이 홀수점의 개수가 0, 2개가 아닐 경우에는 한붓그리기를 할 수 없다.


다시 정리해서 한붓그리기가 가능하려면
(1) 모든 점이 짝수점만으로 되어있거나
(2) 홀수점이 2개여서 하나를 출발점, 나머지 하나를 도착점으로 해야 한다.



쾨니히스베르크의 다리 문제는 A, B, C, D 4개의 점을 잇는 7개의 선으로 표현할 수 있다. 여기서 A는 선이 3개로 홀수점, B는 선이 5개로 홀수점, C도 선이 3개로 홀수점, D 역시 선이 3개로 홀수점이다. 따라서 홀수점이 4개이므로 “쾨니히스베르크의 다리 중 같은 다리를 두 번 건너지 않고, 모든 다리를 한 번씩 건너 산책하는 것은 불가능하다”고 오일러가 증명한 것이다.








모든 다리를 한 번씩만 건너 산책할 수 있도록

다리를 1개 더 건설하라!



그렇다면 다리를 1개 더 건설할 경우 한붓그리기, 다시 말해 모든 다리를 한 번씩만 건너서 산책하는 게 가능해질까? 


홀수점이 없거나 2개가 되도록 다리를 건설하면 한붓그리기가 될 수 있다. 다음과 같이 홀수점 2개를 연결하여 짝수점이 되도록 하면 남은 홀수점은 2개가 되므로 한붓그리기가 가능하다.




(예시)




따라서 위와 같이 다리를 1개 더 건설하면 모든 다리를 한 번씩만 건너서 산책할 수 있다.



0 댓글0
추천콘텐츠
TOP으로 이동