Konigsberg's bridge problem, Seven bridge of Konigsberg
괜히 헛수고하는 다리
목차
1 개요
프레겔 강이 흐르는 쾨니히스베르크[1]의 하중도로 이루어진 독특한 지형과 이 강을 건너기 위해 건설된 일곱 개의 다리에서 시작된 문제로, 한붓그리기로 유명한 문제이다. 그리고 사소한 생각 하나가 여러 사람 피곤하게 만든다는 훌륭한 사례이다. 도대체 누가 생각해낸 것인지 궁금해지는 괴상한 문제 하나가 수많은 수학자들을 괴롭혔다.(...) 별거 아닌 것이 무슨 도시전설로 굳어져 내려오면서 대대로 골치를 썩혀왔으며, 수학의 새로운 분야를 창조하기 까지한 참 대단한 떡밥이다. 심지어 이 새로운 분야는 현대에 와서 더욱 중요해졌다.
2 문제
쾨니히스베르크의 지형과 다리의 모식도.
이 문제를 가장 처음으로 제시한 사람이 누구인지는 알려져 있지 않다. 어쨌든 언제부터인가 "임의의 지점에서 출발하여 일곱 개의 다리를 한 번씩만 건너서 원래 위치로 돌아오는 방법"에 대한 문제가 있었고, 많은 사람들이 이 문제의 답을 찾기 위해 삽질노력을 했다.
3 해답
사실 이 문제의 답은 "그런 방법은 원래 없다". 그래프 이론상으로 한 꼭지점에 이어진 변의 수를 위수라고 하는데, 어떤 연결그래프를 한붓그리기 할 수 있으려면 그 그래프에서 위수가 홀수인 꼭지점이 없거나 있어도 2개만 있어야 하지만(여기선 시작점과 종점이 같기에 모든 꼭지점의 위수가 짝수여야 한다.) 이 문제의 경우 모든 꼭지점에서 위수가 홀수라서 꿈도 희망도 없다.
이 문제의 해답을 찾기 위한 연구의 부산물로 그래프 이론이라는 수학의 한 분야가 생겨났다.(...) 그래프 이론은 네트워크의 발달로 최근에 응용범위가 엄청나게 늘어난 분야이다. 어떤 그래프 이론 교과서도 쾨니히스베르크의 다리 문제는 역사적 배경과 함께 꼭 다루게 된다.
쾨니히스베르크의 다리 건너기는 1735년에 레온하르트 오일러가 가장 처음으로 답이 없다는 것을 증명하였고, 이후 이러한 유형의 문제를 체계적으로 연구하여 일반화시켰다. 이러한 오일러의 공로를 기리기 위해 위상기하학이나 전산학 분야에서는 이와 같은 문제를 오일러 경로(Euler path) 문제라고 표현한다. 그 밖의 분야에서는 "한붓그리기"라고 부르는 편이다.
만약 억지로 다리를 더 놓아서 이 문제를 해결하고자 한다면,
파일:Attachment/Konigsberg Xtended.png
이렇게 다리를 세 개 더 놓으시면 해결 할 수 있다.#
그래프 이론으로 설명할 때 모든지점은 짝수개의 연결로만 이루어져야 원래자리로 돌아올 수 있으므로 두개의 다리만 더 설치하면 된다.
현재 배경이 된 원흉칼리닌그라드의 7개 다리 사이에서 2개는 제2차 세계대전때 폭격으로 소실되었고, 2개는 고속도로를 공사하면서 철거당해 현재는 3개만이 남아있다. 그런데 다리 2개가 폭격으로 날아간 바람에 모든 다리를 한 번씩만 건너서 모두 건널 수 있는 방법[2]이 생겼다. 다만 여전히 임의의 위치에서 시작해서는 해결 할 수 없고, 한번씩만 건너면서 출발점으로 돌아올 수 있는 방법이 없다.
참고로 현재 배경이 된 장소는 이렇게 생겼다. 구글 어스에서 줌을 땡긴 거라 화질이 안 좋으니 양해바람.
4 기타 창작물에서
2007년 3월, 전국연합학력평가에 출제된 바 있다. 의도한 바인지 아닌지는 알 수 없지만 듣기를 살짝 놓치거나 이해하지 못한 학생은 그냥 그렸다.
Q.E.D. 증명종료에서는 이 문제에 대해 '통과할 수 있다.'고 말하였다. 정답은... 저~멀리 돌아가서 강의 원류를 넘어가기. 상식을 비틀어 답을 끌어내는 것, 혹은 수학의 세계와 현실의 세계는 다르다는 것을 비유한 것이라 할 수 있다. 현실은 실전이야 좆만아
네이버 웹툰 n의 등대 - 눈의 등대 편에서 등장한 적이 있다.
스즈미야 하루히의 폭주의 설산증후군 편에서도 짤막하게 언급된다.