문서 보기문서 편집수정 내역 쾨니히스베르크 다리 건너기 문제 (덤프버전으로 되돌리기) [include(틀:이산수학)] [include(틀:기하학·위상수학)] Königsberger Brückenproblem Konigsberg's bridge problem/Seven bridge of Konigsberg [목차] == 개요 == >쾨니히스베르크시의 한 가운데는 프레겔 강[* Pregel. 현재 프레골랴(Преголя) 강]이 흐르고 있고 여기에는 가운데 섬들과 연결되어있는 일곱 개의 다리가 있다. 그 다리들을 '''한 번씩만 차례로 모두 건널 수 있겠는가?''' [[프로이센 왕국]] [[동프로이센]] 주의 [[쾨니히스베르크]] 시(오늘날 [[러시아]] [[칼리닌그라드|칼리닌그라드 주]] [[칼리닌그라드|칼리닌그라드 시]])를 흐르는 프레겔 강에는 크나이프호프[* Kneiphof. 아래 그림에서 중앙에 다섯 개 다리와 연결된 섬. 러시아의 영토가 된 지금은 [[임마누엘 칸트]]의 이름을 따서 칸트 섬으로 개명되었다.] 와 롬세[* Lomse. 아래 그림에서 세 개 다리와 연결된 오른쪽 섬. 왼쪽의 크나이프호프에 비하면 매우 길고 커다란 섬이기에 다리가 놓인 부분만 보여주는 아래 그림에서는 대부분이 잘렸다. [[동프로이센]]이 러시아 땅이 된 현재 이름은 [[10월 혁명]]을 기념하여 옥차브리스키 섬으로 변경되었다. [[칼리닌그라드 스타디움]]이 들어서 있다.]라는 두 [[하중도]]가 있다. 이 독특한 지형의 강을 건너기 위해 일곱 개의 다리가 건설되었는데, 여기에서 시작된 문제. 유명한 [[한붓그리기]] 문제다. 이 문제 하나가 수많은 수학자들을 괴롭혔는데 마치 도시전설처럼 굳어져 내려오면서 대대로 골치를 썩혀왔으며, [[위상수학|수학의 새로운 분야]]를 창조하기까지 했으며 이 새로운 분야는 [[위상부도체|현대에 와서]]는 [[푸앵카레 추측]]으로 더 중요해진다. == 문제 == [[파일:external/upload.wikimedia.org/Konigsberg_bridges.png]] [[쾨니히스베르크]]의 지형과 다리의 모식도. 이 문제를 가장 처음으로 제시한 사람이 누구인지는 알려져 있지 않다. 어쨌든 언제부터인가 "임의의 지점에서 출발하여 일곱 개의 다리를 한 번씩만 건너서 원래 위치로 돌아오는 방법"에 대한 문제가 있었고, 많은 사람들이 이 문제의 답을 찾기 위해 노력을 했다. == 해답 == ||<tablealign=center><tablebordercolor=#458bd0>{{{#!wiki style="margin: -5px -10px" [youtube(a9tZ-iU_Nco, start=238)]}}}|| ||<bgcolor=#458bd0> {{{#fff '''레온하르트 오일러가 제시한 해답'''}}} || 답은 '''"없다"'''이다. 직접 해 보려고 동선을 어떻게 그어도 다리 하나가 항상 건너지 못한 채로 남아 있게 된다. 당시 [[레온하르트 오일러]]는 이 문제를 다음 그림과 형태로 각각의 다리에 a부터 g까지 이름을 부여하고 도식화해 1735년에 논문을 발표했다. [[파일:4-12-2.png|width=400]] 논문에 포함된 이 스케치는 현대에 이르러 그래프 구조의 원형이 되었다. 오일러의 스케치를 현대식 그래프 구조에 따라 나타낸 아래 그림에서는 A부터 D까지를 정점(Vertex), a부터 g까지는 간선(Edge)으로 구성된 그래프라는 수학적 구조를 찾아볼 수 있다. [[파일:4-12-3.png|width=400]] 오일러는 모든 정점이 짝수 개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다. 그로부터 100년이 훨씬 더 지난 1873년, 독일의 수학자 칼 히어홀저(Carl Hierholzer)가 이를 수학적으로 증명해낸다. 이를 오일러의 정리(Euler's Theorem)라 부른다. 아울러 모든 간선을 한 번씩 방문하는 유한 그래프(Finite Graph)를 일컬어 오일러 경로(Eulerian Trail/Eulerian Path)라 부르며, 어려서부터 즐겨 하던 놀이 중 하나인 [[한붓그리기]]라고도 말한다. 글자 그대로 한 번도 붓을 떼지 않고 모든 간선을 한 번씩만 그릴 수 있는지를 의미한다. 그리고 마지막으로 가장 중요한 사항으로, 증명에 따르면 쾨니히스베르크의 다리는 모든 정점이 짝수개의 차수를 갖지 않으므로(심지어 짝수개의 차수를 갖는 정점은 하나도 없다) 오일러 경로가 아니다. 오일러는 어떤 그래프의 한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한번씩만 지나서 처음 출발점으로 되돌아오는 길을 가지려면 각 꼭짓점에 연결된 변의 개수가 모두 짝수여야 함을 증명했다.[* 참고로 출발점으로 돌아올 필요가 없으면 홀수점이 두 개일 때도 성립한다.] 짝수여야 하는 이유는, 들어감-나감-들어감-나감-...(출발점에 한해서 나감-들어감-나감-들어감-...)의 구조가 반복되어 '나감'으로 끝나야 다른 점으로 이동할 수 있고 마지막 도착점이기도 한 출발점은 '들어감'으로 끝나야 그 점에서 멈출 수 있기 때문이다. 하지만 위의 문제의 경우 꼭짓점의 수가 홀수, 즉 들어감-나감-'''들어감'''으로 끝나기 때문에 어디서든지 시작해도 나갈 수 없다. 아무리 가짓수가 많아도 홀수라면 결국엔 '들어감'(출발점이라면 '나감')으로 끝나기 때문에 출발점으로 되돌아올 수 없게 된다. 따라서 오일러 경로가 성립되지 않는다. 단, 홀수점이 2개일 때는 그 두 개의 홀수점을 각각 출발점과 도착점으로 할 경우에 한해서 한붓그리기는 가능하며, 이러한 경로는 출발점으로 다시 되돌아오는 것이 아니므로 오일러 경로는 아니지만, 모든 변을 한 번씩만 지나기 때문에 오일러 경로에 준하다는 의미로 'Semi-Euler path'라고 한다. '''이 문제의 해답을 찾기 위한 연구의 부산물로 그래프 이론이라는 수학의 한 분야가 생겨났다.''' 그래프 이론은 네트워크의 발달로 최근에 응용범위가 엄청나게 늘어난 분야이다. 어떤 그래프 이론 교과서든 쾨니히스베르크의 다리 문제는 역사적 배경과 함께 꼭 다루게 된다. 쾨니히스베르크의 다리 건너기는 1735년에 [[레온하르트 오일러]]가 가장 처음으로 [[답이 없다]]는 것을 증명하였고, 이후 이러한 유형의 문제를 체계적으로 연구하여 일반화시켰다. 이러한 오일러의 공로를 기리기 위해 위상기하학이나 전산학 분야에서는 이와 같은 문제를 오일러 경로(Euler path) 문제라고 표현한다. 만약 다리를 더 놓을 수 있다는 조건이 추가로 붙는다면, [[파일:attachment/Konigsberg_Xtended.png]] 이렇게 다리를 세 개 더 놓으면 해결 할 수 있다.[[http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg|#]] 그래프 이론으로는 설명할 때 모든 지점은 짝수 개의 연결로만 이루어져야 원래 자리로 돌아올 수 있으므로 두 개의 다리만 더 설치하면 된다. 그리고 '한붓그리기' ㅡ 꼭 원래 위치로 돌아올 필요없이 단순히 '한 번씩만 건너는' 데에만 한정한다면 아무 데나 다리를 하나만 더 놓아주거나, 다리 하나를 없애면 해결할수 있다. == 현재 칼리닌그라드에서 다리 한 번씩 건너기 == 배경이 된 장소의 현재 모습은 위성지도로 이렇게 생겼다. [[파일:쾨니히스베르크의 다리.jpg]] [[https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg#/media/File:Present_state_of_the_Seven_Bridges_of_K%C3%B6nigsberg.png|좀더 알아보기 쉬운 버전]] 북위 54도 42' 23.53'' 동경 20도 30'37.08 보다시피 배경이 된 [[칼리닌그라드]]의 다리는 5개 밖에 남지 않았다. 7개 다리 중에서 2개는 [[동프로이센 공세]] 당시 [[이오시프 스탈린]]의 명령으로 [[소련군]]의 폭격이 진행되면서 소실되었고, 또 2개는 이후 [[고속도로]]로 대체 당해 원본 다리는 3개만이 남아있다. 아무튼 [[고르디우스의 매듭|스탈린이 다리 두개를 폭격으로 날린 바람에 5개밖에 남지 않아 모든 다리를 한 번씩만 건너서 모두 건널 수 있는 방법이 생겼다.]] 다만 여전히 임의의 위치에서 시작해서는 해결 할 수 없고, 특정 위치에서만 가능하다. 상단의 위성사진 중앙에 보이는 섬 혹은 그 오른쪽에 있는 본토 2개를 말한다. 이를 도형으로 그리면 θ 형태가 되는데, 이 가로선의 양끝에 있는 두 꼭지점 모두 선이 3개 연결되어 있어서 각각 출발점-도착점 역할을 하기 때문이다. 주파 방법은 당연히 5 혹은 그 반대인 2를 그리듯이 움직이는 것이다. 또한 한 번씩만 건너면서 출발점으로 돌아올 수 있는 방법은 없다. 상술한 두 꼭지점 모두 "나감-들어감-'''나감'''"으로 끝나기 때문에 절대로 출발점으로 돌아올 수 없기 때문이다. 따라서 [[한붓그리기]] 문제에서는 답이 있어도 오일러 경로 문제에서는 여전히 불가능하기 때문에 Semi-Euler path라고 부른다. 갈림길의 수가 홀수인 두 지점 가운데 하나에서 출발해서 반대편 지점에서 끝나는 방식이기 때문. == 기타 창작물에서 == [[2007년]] 3월, [[전국연합학력평가]]에 출제된 바 있다. 의도한 바인지 아닌지는 알 수 없지만 듣기를 살짝 놓치거나 이해하지 못한 학생은 그냥 그렸다. [[Q.E.D. 증명종료]]에서는 이 문제에 대해 '통과할 수 있다.'고 말하였다. 정답은 저~멀리 돌아가서 '''강의 원류를 넘어가기'''. 하지만 이는 실제로는 '''불가능'''한데, 그바르데이스크라는 곳에서 강이 두 개의 하류로 갈라지기 때문이다. 글로 설명하면 이해가 어려운데, 지도를 보면 한 눈에 이해할 수 있다. [[파일:konigs.png]] 즉, 실제로는 [[칼리닌그라드]] 북부를 포함한 땅덩어리가 하나의 거대한 섬[* 단, 2개로 나눠진 강으로 인해 육지와 나눠진 곳은 섬으로 보지 않기도 한다.]으로, 그바르데이스크[* 동프로이센 시기 독일어 이름은 타피아우(Tapiau), 지금도 이 곳에 위치한 성인 타피아우 성에 그 이름이 남아있다.]에서 갈라지는 데이마강을 넘어가지 않고서는 강의 원류를 돌아간다는 행위 자체가 아예 불가능하다. 그냥 문학적 허구라고 이해하면 편할 것이다. 애초에 이 문제 자체가 처음부터 이를 고려해서 만들어진 것. 사실 프레골랴강이 흘러들어가는 비스툴라 [[석호]]를 [[발트해]]로 이어주는 물길이 13세기 말부터 15세기 말까지 단절되었던 적이 있기에 그 당시의 [[https://ko.wikipedia.org/wiki/%EB%B9%84%EC%8A%A4%ED%88%B4%EB%9D%BC%EA%B3%B6|비스툴라곶]]을 건넌다면 가능했을지도 모르나, 그 때에는 이 문제는 물론이요 다리가 있는 [[쾨니히스베르크]] 시 자체가 세워지기도 전이었다. [[네이버 웹툰]] [[N의 등대]] - 눈의 등대 편에서 등장한 적이 있다. 쾨니히스베르크 다리 건너기 문제와 똑같은 섬과 다리가 있는 곳에서 지도를 건네주며 '다리는 하루에 한 번씩 건널 수 있고 한 번 건넌 다리는 건널 수 없다'며 원본과 똑같은 문제를 제시하나, 원본과 똑같으면 당연히 풀 수 없으므로 '딱 한 번 두 명이 동시에, 건넜던 다리를 건너는 게 가능하다'란 추가 룰을 제시한다.[*스포일러 다리는 지도와 눈에 보이는 게 다가 아니었고 일정 시간에만 밀물, 썰물 작용으로 드러났다가 사라지는 다리가 존재했다. 즉, 이 다리의 존재를 알고 이용한다면 굳이 번거로운 추가 룰을 쓸 이유가 없다.] [[세미와 매직큐브]] 3화에서 세미 일행과 만난 레온하르트 오일러가 언급한다. [[분류:이산수학]][[분류:퀴즈]][[분류:레온하르트 오일러]]캡챠되돌리기