| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오(예상과 확인) · 불 논리 · 브라에스 역설 · 포함-배제의 원리 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
Königsberger Brückenproblem (독일어)
Задача о семи кёнигсбергских мостах (러시아어)
Konigsberg's bridge problem/Seven bridge of Konigsberg (영어)
1. 개요
쾨니히스베르크시의 한 가운데는 프레겔강[1]이 흐르고 있고 여기에는 가운데 섬들과 연결되어있는 일곱 개의 다리가 있다. 그 다리들을 한 번씩만 차례로 모두 건널 수 있겠는가?
프로이센 왕국 동프로이센주의 쾨니히스베르크시(오늘날 러시아 칼리닌그라드주 칼리닌그라드시)를 흐르는 프레겔강에는 크나이프호프[2]와 롬세[3]라는 두 하중도가 있다. 이 독특한 지형의 강을 건너기 위해 일곱 개의 다리가 건설되었는데, 여기에서 시작된 문제. 유명한 한붓그리기 문제다.
도시전설처럼 내려오면서 수많은 수학자들을 괴롭힌 끝에, 수학의 새로운 분야인 위상수학이 생겨나는 데에 한몫했다. 이 새로운 분야는 현대에 와서는 푸앵카레 추측으로 더 중요해진다.
2. 문제
쾨니히스베르크의 지형과 다리의 모식도.
이 문제를 가장 처음으로 제시한 사람이 누구인지는 알려져 있지 않다. 어쨌든 언제부터인가 "임의의 지점에서 출발하여 일곱 개의 다리를 한 번씩만 건너서 원래 위치로 돌아오는 방법"에 대한 문제가 있었고, 많은 사람들이 이 문제의 답을 찾기 위해 노력을 했다.
3. 해답과 증명
결론부터 말하자면 답은 "없다". 물론 여기에서 정확한 해답을 내려면 그 "불가능한 이유를 증명"하는게 진정한 해답이다.| 레온하르트 오일러가 제시한 해답 |
논문에 포함된 이 스케치는 현대에 이르러 그래프 구조의 원형이 되었다. 오일러의 스케치를 현대식 그래프 구조에 따라 나타낸 아래 그림에서는 A부터 D까지를 정점(Vertex), a부터 g까지는 간선(Edge)으로 구성된 그래프라는 수학적 구조를 찾아볼 수 있다.
오일러는 모든 다리를 한 번씩만 건너려면, 모든 정점이 짝수 차수(Degree)를 가지거나, 홀수 차수를 가진 정점이 정확히 2개 존재해야 한다는 것을 증명하였다. 그로부터 100년이 훨씬 지난 1873년, 독일의 수학자 칼 히어홀저(Carl Hierholzer)는 이 명제의 역, 즉 홀수 차수를 가진 정점이 없거나 정확히 2개일 경우 반드시 모든 다리를 한 번씩 건널 수 있다는 사실을 수학적으로 증명하였다. 이로써 필요충분조건이 완성되었으며, 이를 오일러의 정리(Euler's Theorem)라 부른다.
또한, 모든 간선을 한 번씩만 방문하는 유한 그래프(Finite Graph)를 오일러 경로(Eulerian Trail/Eulerian Path)라 하며, 어릴 때 자주 하던 놀이인 ‘한붓그리기’라고도 부른다. 이는 글자 그대로, 한 번도 붓을 떼지 않고 모든 간선을 정확히 한 번씩만 그릴 수 있는지를 의미한다. 그리고 가장 중요한 점은, 오일러의 증명에 따르면 쾨니히스베르크의 다리 문제에서는 홀수 차수를 가진 정점이 4개 존재하고(게다가 짝수 차수를 가지는 정점은 하나도 없다), 따라서 모든 다리를 단 한 번씩 건너는 것은 불가능하다는 것이다.
오일러의 증명은 다음과 같다. 다리를 건너는 과정은 각 정점마다 '들어감–나감–들어감–나감–…'의 구조로 반복된다. (출발점에서는 '나감–들어감–나감–들어감–…'의 형태가 된다.) 이동하려면 '나감'으로 끝나야 하고, 마지막 도착점은 '들어감'으로 끝나야 이동을 마칠 수 있다.
하지만 아무리 차수가 많더라도 정점의 차수가 홀수이면, '들어감–나감–들어감'(또는 출발점에서는 '나감–들어감–나감')으로 끝나게 된다. 즉, 홀수 차수를 가진 정점이 2개를 초과하면 '들어감'으로 끝나야 하는 정점이 1개를 넘게 되므로, 오일러 경로가 존재할 수 없게 된다. 반대로 홀수 차수를 가진 정점이 없으면 아무 점에서 시작해 같은 점으로 돌아오는 오일러 경로가 존재하며, 홀수 차수를 가진 정점이 2개 있을 경우에는 그 두 점을 각각 출발점과 도착점으로 삼아 오일러 경로를 구성할 수 있다.
이 문제의 해답을 찾기 위한 연구의 부산물로 그래프 이론이라는 수학의 한 분야가 생겨났다. 그래프 이론은 네트워크의 발달로 최근에 응용범위가 엄청나게 늘어난 분야이다. 어떤 그래프 이론 교과서든 쾨니히스베르크의 다리 문제는 역사적 배경과 함께 꼭 다루게 된다.
쾨니히스베르크의 다리 건너기는 1735년에 레온하르트 오일러가 가장 처음으로 답이 없다는 것을 증명하였고, 이후 이러한 유형의 문제를 체계적으로 연구하여 일반화시켰다. 이러한 오일러의 공로를 기리기 위해 위상기하학이나 전산학 분야에서는 이와 같은 문제를 오일러 경로(Euler path) 문제라고 표현한다.
만약 다리를 더 놓을 수 있다는 조건이 추가로 붙는다면,
이렇게 다리를 세 개 더 놓으면 해결 할 수 있다.# 그래프 이론으로는 설명할 때 모든 지점은 짝수 개의 연결로만 이루어져야 원래 자리로 돌아올 수 있으므로 두 개의 다리만 더 설치하면 된다. 그리고 '한붓그리기' ㅡ 꼭 원래 위치로 돌아올 필요없이 단순히 '한 번씩만 건너는' 데에만 한정한다면 아무 데나 다리를 하나만 더 놓아주거나, 다리 하나를 없애면 해결할수 있다.
4. 현재 칼리닌그라드에서 다리 한 번씩 건너기
배경이 된 칼리닌그라드의 다리는 현재 5개만 남아있다. 7개 중에서 2개는 동프로이센 공세 당시 이오시프 스탈린의 명령으로 소련군의 폭격이 진행되면서 소실되었고, 또 2개는 이후 고속도로로 대체되어 원본 다리는 3개만이 남아있다. 아무튼 스탈린이 다리 2개를 폭격으로 날린 바람에 모든 다리를 한 번씩만 건너서 모두 건널 수 있는 방법이 생겼다.
다만 여전히 임의의 위치에서 시작해서는 해결할 수 없고, 특정 위치에서만 가능하다. 상단의 위성사진 중앙에 보이는 섬 혹은 그 오른쪽에 있는 본토 2개를 말한다. 이를 도형으로 그리면 θ 형태가 되는데, 이 가로선의 양끝에 있는 두 꼭지점 모두 선이 3개 연결되어서 각각 출발점-도착점 역할을 하기 때문이다. 주파 방법은 당연히 5 혹은 그 반대인 2를 그리듯이 움직이는 것이다.
넷상에서는 우스개소리로 이때의 스탈린을 두고 '기적의 수학자'라 부른다. #1 #2 고르디우스의 매듭을 끊어서 해결(?)해버린 알렉산드로스 대왕마냥 다리를 파괴해서 방법이 열렸기 때문이다.
5. 기타 창작물에서
Q.E.D. 증명종료에서는 이 문제에 대해 '통과할 수 있다.'고 말하였다. 정답은 저~멀리 돌아가서 강의 원류를 넘어가기. 하지만 이는 실제로는 불가능한데, 그바르데이스크라는 곳에서 강이 두 개의 하류로 갈라지기 때문이다. 글로 설명하면 이해가 어려운데, 지도를 보면 한 눈에 이해할 수 있다.[4]즉, 실제로는 칼리닌그라드 북부를 포함한 땅덩어리가 하나의 거대한 섬[5]으로, 그바르데이스크[6]에서 갈라지는 데이마강을 넘어가지 않고서는 강의 원류를 돌아간다는 행위 자체가 아예 불가능하다. 프레골랴강이 흘러들어가는 비스툴라 석호를 발트해로 이어주는 물길이 13세기 말부터 15세기 말까지 단절되었던 적이 있기에 그 당시의 비스툴라곶을 건넌다면 가능했을지도 모르나, 그 때에는 이 문제는 물론이요 다리가 있는 쾨니히스베르크 시 자체가 세워지기도 전이었다.
네이버 웹툰 N의 등대 - 눈의 등대 편에서 등장한 적이 있다. 쾨니히스베르크 다리 건너기 문제와 똑같은 섬과 다리가 있는 곳에서 지도를 건네주며 '다리는 하루에 한 번씩 건널 수 있고 한 번 건넌 다리는 건널 수 없다'며 원본과 똑같은 문제를 제시하나, 원본과 똑같으면 당연히 풀 수 없으므로 '딱 한 번 두 명이 동시에, 건넜던 다리를 건너는 게 가능하다'란 추가 룰을 제시한다.[스포일러]
세미와 매직큐브 3화에서 세미 일행과 만난 레온하르트 오일러가 언급한다.
[1] Pregel. 현재 프레골랴(Преголя) 강[2] Kneiphof. 아래 그림에서 중앙에 다섯 개 다리와 연결된 섬. 러시아의 영토가 된 지금은 임마누엘 칸트의 이름을 따서 칸트 섬으로 개명되었다. 쾨니히스베르크 대성당이 위치해있다.[3] Lomse. 아래 그림에서 세 개 다리와 연결된 오른쪽 섬. 왼쪽의 크나이프호프에 비하면 매우 길고 커다란 섬이기에 다리가 놓인 부분만 보여주는 아래 그림에서는 대부분이 잘렸다. 동프로이센이 러시아 땅이 된 현재 이름은 10월 혁명을 기념하여 옥탸브리스키섬으로 변경되었다. 칼리닌그라드 스타디움이 들어서 있다.[4] 정확히는 작중에 나오는 시체가 발견된 사건에 대한 응용이었지만[5] 단, 2개로 나눠진 강으로 인해 육지와 나눠진 곳은 섬으로 보지 않기도 한다.[6] 동프로이센 시기 독일어 이름은 타피아우(Tapiau), 지금도 이 곳에 위치한 성인 타피아우 성에 그 이름이 남아있다.[스포일러] 다리는 지도와 눈에 보이는 게 다가 아니었고 일정 시간에만 밀물, 썰물 작용으로 드러났다가 사라지는 다리가 존재했다. 즉, 이 다리의 존재를 알고 이용한다면 굳이 번거로운 추가 룰을 쓸 이유가 없다.