쾨니히스베르크 다리 건너기 문제 > 유용한 정보

쾨니히스베르크시의 한 가운데는 프레골라 강이 흐르고 있고 여기에는 가운데 섬들과 연결되어있는 일곱 개의 다리가 있다. 그 다리들을 어느 다리나  한번씩만 차례로 모두 건널 수 있겠는가? 

프레겔 강이 흐르는 쾨니히스베르크 의 하중도로 이루어진 독특한 지형과 이 강을 건너기 위해 건설된 일곱 개의 다리에서 시작된 문제로, 한붓그리기로 유명한 문제이다. 

도대체 누가 생각해낸 것인지 궁금해지는 괴상한 문제 하나가 수많은 수학자들을 괴롭혔다.(...) 

별거 아닌 것이 무슨 도시전설로 굳어져 내려오면서 대대로 골치를 썩혀왔으며, 

수학의 새로운 분야를 창조하기 까지한 참 대단한 떡밥이다. 

심지어 이 새로운 분야는 현대에 와서 더욱 중요해졌다. 

쾨니히스베르크의 지형과 다리의 모식도.

이 문제를 가장 처음으로 제시한 사람이 누구인지는 알려져 있지 않다. 어쨌든 언제부터인가 "임의의 지점에서 출발하여 일곱 개의 다리를 한 번씩만 건너서 원래 위치로 돌아오는 방법"에 대한 문제가 있었고, 많은 사람들이 이 문제의 답을 찾기 위해 노력을 했다.

-해답-

사실 이 문제의 답은 "그런 방법은 원래 없다". 오일러는 어떤 그래프의 한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한번씩만 지나서 처음 출발점으로 되돌아오는 길을 가지려면 각 꼭짓점에 연결된 변의 개수가 모두 짝수이어야 함을 증명했다.

짝수여야 하는 이유는, 들어감-나감-들어감-나감(이하 생략)의 구조가 반복됨으로 다른 점으로 이동할 수 있기 때문이다. 하지만 위의 문제의 경우 꼭짓점의 수가 홀수, 즉 들어감-나감-들어감으로 끝나기 때문에 어디서든지 시작해도 나갈 수 없다. 아무리 가짓수가 많아도 홀수라면 결국엔 '들어감'으로 끝난다.

이 문제의 해답을 찾기 위한 연구의 부산물로 그래프 이론이라는 수학의 한 분야가 생겨났다 . 그래프 이론은 네트워크의 발달로 최근에 응용범위가 엄청나게 늘어난 분야이다. 어떤 그래프 이론 교과서든 쾨니히스베르크의 다리 문제는 역사적 배경과 함께 꼭 다루게 된다. 

쾨니히스베르크의 다리 건너기는 1735년에 레 온하르트 오일러가 가장 처음으로 답이 없다는 것을 증명하였고, 이후 이러한 유형의 문제를 체계적으로 연구하여 일반화시켰다. 이러한 오일러의 공로를 기리기 위해 위상기하학이나 전산학 분야에서는 이와 같은 문제를 오일러 경로(Euler path) 문제 라고 표현한다. 그 밖의 분야에서는 "한붓그리기"라고 부르는 편이다.

만약 억지로 다리를 더 놓아서 이 문제를 해결하고자 한다면,

이렇게 다리를 세 개 더 놓으면 해결 할 수 있다. 

그래프 이론으로는 설명할 때 모든 지점은 짝수 개의 연결로만 이루어져야 원래 자리로 돌아올 수 있으므로 두 개의 다리만 더 설치하면 된다. 그리고 '한붓그리기' ㅡ 꼭 원래 위치로 돌아올 필요없이 단순히 '한 번씩만 건너는' 데에만 한정한다면 아무데나 다리를 하나만 더 놓아주면 된다.

현재 배경이 된 칼리닌그라드의 7개 다리 사이에서 2개는 제2차 세계 대전때 폭격으로 소실되었고, 2개는 고속도로를 공사하면서 철거당해 현재는 3개만이 남아있다. 그런데 다리 2개가 폭격으로 날아간 바람에 모든 다리를 한 번씩만 건너서 모두 건널 수 있는 방법이 생겼다. 기적의 수학자 서기장 동무 다만 여전히 임의의 위치에서 시작해서는 해결 할 수 없고, 한 번씩만 건너면서 출발점으로 돌아올 수 있는 방법이 없다.

출처:나무위키

문제가 수학 이론으로 까지 발전한 좋은예