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