[include(틀:이산수학·수리논리학)] Königsberger Brückenproblem Konigsberg's bridge problem/Seven bridge of Konigsberg [목차] == 개요 == >쾨니히스베르크시의 한 가운데는 프레골라 강이 흐르고 있고 여기에는 가운데 섬들과 연결되어있는 일곱 개의 다리가 있다. 그 다리들을 '''한 번씩만 차례로 모두 건널 수 있겠는가?''' [[프로이센 왕국]] [[동프로이센]]의 [[쾨니히스베르크]] 시(오늘날 [[러시아]] [[칼리닌그라드|칼리닌그라드 주]] [[칼리닌그라드]] 시)를 흐르는 프레겔 강에는 크나이프호프[* 아래 그림에서 중앙에 다섯 개 다리와 연결된 섬.] 와 롬세[* 아래 그림에서 세 개 다리와 연결된 오른쪽 섬. 왼쪽의 크나이프호프에 비하면 매우 길고 커다란 섬이기에 다리가 놓인 부분만 보여주는 아래 그림에서는 대부분이 잘렸다. [[동프로이센]]이 러시아 땅이 된 현재 이름은 옥차브리스키 섬으로 변경되었다.]라는 두 [[하중도]]가 있다. 이 독특한 지형의 강을 건너기 위해 일곱 개의 다리가 건설되었는데, 여기에서 시작된 문제. 유명한 [[한붓그리기]] 문제다. 도대체 누가 생각해낸 것인지 궁금해지는 이 괴상한 문제 하나가 수많은 수학자들을 괴롭혔다. 별거 아닌 것이 무슨 도시전설로 굳어져 내려오면서 대대로 골치를 썩혀왔으며, [[위상수학|수학의 새로운 분야]]를 창조하기까지 한 참 대단한 떡밥이다. 심지어 이 새로운 분야는 [[위상부도체|현대에 와서]]는 [[푸앵카레 추측|더욱 중요해졌다]]. == 문제 == [[파일:external/upload.wikimedia.org/Konigsberg_bridges.png]] [[쾨니히스베르크]]의 지형과 다리의 모식도. 이 문제를 가장 처음으로 제시한 사람이 누구인지는 알려져 있지 않다. 어쨌든 언제부터인가 "임의의 지점에서 출발하여 일곱 개의 다리를 한 번씩만 건너서 원래 위치로 돌아오는 방법"에 대한 문제가 있었고, 많은 사람들이 이 문제의 답을 찾기 위해 노력을 했다. == 해답 == 사실 이 문제의 답은 '''"[[그런 거 없다|그런 방법은 원래 없다]]"'''이다. 직접 해 보려고 동선을 어떻게 그어도 다리 하나가 항상 건너지 못한 채로 남아 있게 된다. 당시 오일러는 이 문제를 다음 그림과 형태로 각각의 다리에 a부터 g까지 이름을 부여하고 도식화해 1735년에 논문을 발표했다. [[파일:4-12-2.png|width=400]] 논문에 포함된 이 스케치는 현대에 이르러 그래프 구조의 원형이 되었다. 오일러의 스케치를 현대식 그래프 구조에 따라 나타낸 아래 그림에서는 A부터 D까지를 정점(Vertex), a부터 g까지는 간선(Edge)으로 구성된 그래프라는 수학적 구조를 찾아볼 수 있다. [[파일:4-12-3.png|width=400]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.319, 책만, 2020 오일러는 모든 정점이 짝수 개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다. 그로부터 100년이 훨씬 더 지난 1873년, 독일의 수학 자 칼 히어홀저(Carl Hierholzer)가 이를 수학적으로 증명해낸다. 이를 오일러의 정리(Euler's Theorem)라 부른다. 아울러 모든 간선을 한 번씩 방문하는 유한 그래프(Finite Graph)를 일컬 어 오일러 경로(Eulerian Trail/Eulerian Path)라 부르며, 어려서부터 즐겨 하던 놀이 중 하나인 [[한붓그리기]]라고도 말한다. 글자 그대로 한 번도 붓을 떼지 않고 모든 간선을 한 번씩만 그릴 수 있는지를 의미한다. 그리고 마지막으로 가장 중요한 사항으로, 증명에 따르면 쾨니히스베르크의 다리는 모든 정점이 짝수개의 차수를 갖지 않으므로(심지어 짝수개의 차수를 갖는 정점은 하나도 없다) 오일러 경로가 아니다. 오일러는 어떤 그래프의 한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한번씩만 지나서 처음 출발점으로 되돌아오는 길을 가지려면 각 꼭짓점에 연결된 변의 개수가 모두 짝수여야 함을 증명했다.[* 참고로 출발점으로 돌아올 필요가 없으면 홀수점이 두 개일 때도 성립한다.] 짝수여야 하는 이유는, 들어감-나감-들어감-나감(이하 생략)의 구조가 반복됨으로 다른 점으로 이동할 수 있기 때문이다. 하지만 위의 문제의 경우 꼭짓점의 수가 홀수, 즉 들어감-나감-'''들어감'''으로 끝나기 때문에 [[들어올 때는 마음대로였겠지만 나갈 때는 아니란다|어디서든지 시작해도 나갈 수 없다.]] 아무리 가짓수가 많아도 홀수라면 결국엔 '들어감'으로 끝난다. 따라서 홀수점이 2개를 초과하는 경우는 한붓그리기가 불가능하며 홀수점이 2개일 때는 그 두 개의 홀수점을 출발점과 도착점으로 해야 한다. '''이 문제의 해답을 찾기 위한 연구의 부산물로 그래프 이론이라는 수학의 한 분야가 생겨났다.''' 그래프 이론은 네트워크의 발달로 최근에 응용범위가 엄청나게 늘어난 분야이다. 어떤 그래프 이론 교과서든 쾨니히스베르크의 다리 문제는 역사적 배경과 함께 꼭 다루게 된다. 쾨니히스베르크의 다리 건너기는 1735년에 [[레온하르트 오일러]]가 가장 처음으로 [[답이 없다]]는 것을 증명하였고, 이후 이러한 유형의 문제를 체계적으로 연구하여 일반화시켰다. 이러한 오일러의 공로를 기리기 위해 위상기하학이나 전산학 분야에서는 이와 같은 문제를 오일러 경로(Euler path) 문제라고 표현한다. 그 밖의 분야에서는 "[[한붓그리기]]"라고 부르는 편이다. 만약 다리를 더 놓을 수 있다는 조건이 추가로 붙는다면, [[파일:attachment/Konigsberg_Xtended.png]] 이렇게 다리를 세 개 더 놓으면 해결 할 수 있다.[[http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg|#]] 그래프 이론으로는 설명할 때 모든 지점은 짝수 개의 연결로만 이루어져야 원래 자리로 돌아올 수 있으므로 두 개의 다리만 더 설치하면 된다. 그리고 '한붓그리기' ㅡ 꼭 원래 위치로 돌아올 필요없이 단순히 '한 번씩만 건너는' 데에만 한정한다면 아무데나 다리를 하나만 더 놓아주던가, [[제2차 세계 대전|폭격으로 두 개를 삭제]]하면 된다. 그리고 두 하중도를 잇는 다리 하나만 삭제해도 해결할수 있다. == 현재 == 배경이 된 장소의 현재 모습은 위성지도로 이렇게 생겼다. [[파일:쾨니히스베르크의 다리.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개밖에 남지 않아 '''모든 다리를 한 번씩만 건너서 모두 건널 수 있는 방법이 생겨버렸다'''. 진정한 의미의 [[이오시프 스탈린|기적의 수학자]](...) 다만 여전히 임의의 위치에서 시작해서는 해결 할 수 없고, 한 번씩만 건너면서 출발점으로 돌아올 수 있는 방법은 없다. 즉, [[한붓그리기]] 문제에서는 답이 있다고 하지만, 오일러 경로 문제에서는 Semi-Euler path라고 부른다. 갈림길의 수가 홀수인 두 지점 가운데 하나에서 출발해서 반대편 지점에서 끝나는 방식이기 때문. == 기타 창작물에서 == [[2007년]] 3월, [[전국연합학력평가]]에 출제된 바 있다. 의도한 바인지 아닌지는 알 수 없지만 듣기를 살짝 놓치거나 이해하지 못한 학생은 그냥 그렸다. [[Q.E.D. 증명종료]]에서는 이 문제에 대해 '통과할 수 있다.'고 말하였다. 정답은 저~멀리 돌아가서 '''강의 원류를 넘어가기'''. 상식을 비틀어 답을 끌어내는 것, 혹은 수학의 세계와 현실의 세계는 다르다는 것을 비유한 것이라 할 수 있다. 하지만 이는 실제로는 '''불가능'''한데, 그바르데이스크라는 곳에서 강이 두 개의 하류로 갈라지기 때문이다. 글로 설명하면 이해가 어려운데, 지도를 보면 한 눈에 이해할 수 있다. [[파일:konigs.png]] 즉, 실제로는 [[칼리닌그라드]] 북부를 포함한 땅덩어리가 '''[[김포섬|하나의 거대한 섬]]'''으로, 그바르데이스크[* 동프로이센 시기 독일어 이름은 타피아우(Tapiau), 지금도 이 곳에 위치한 성인 타피아우 성에 그 이름이 남아있다.]에서 갈라지는 데이마강을 넘어가지 않고서는 강의 원류를 돌아간다는 행위 자체가 아예 불가능하다. 애초에 이 문제 자체가 처음부터 이를 고려해서 만들어진 것.--강 아래를 땅굴을 파서 넘어간다면 얘기는 달라진다-- [[네이버 웹툰]] [[N의 등대]] - 눈의 등대 편에서 등장한 적이 있다. 쾨니히스베르크 다리 건너기 문제와 똑같은 섬과 다리가 있는 곳에서 지도를 건네주며 '다리는 하루에 한 번씩 건널 수 있고 한 번 건넌 다리는 건널 수 없다'며 원본과 똑같은 문제를 제시하나, 원본과 똑같으면 당연히 풀 수 없으므로 '딱 한 번 두 명이 동시에, 건넜던 다리를 건너는 게 가능하다'란 추가 룰을 제시한다.[*스포일러 다리는 지도와 눈에 보이는 게 다가 아니었고 일정 시간에만 밀물, 썰물 작용으로 드러났다가 사라지는 다리가 존재했다. 즉, 이 다리의 존재를 알고 이용한다면 굳이 번거로운 추가 룰을 쓸 이유가 없다.] [[세미와 매직큐브]] 3화에서 세미 일행과 만난 레온하르트 오일러가 언급한다. [[분류:이산수학]][[분류:퀴즈]]