| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | 이론 | |
| <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)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다. 그로부터 100년이 훨씬 더 지난 1873년, 독일의 수학자 칼 히어홀저(Carl Hierholzer)가 이를 수학적으로 증명해낸다. 이를 오일러의 정리(Euler's Theorem)라 부른다. 아울러 모든 간선을 한 번씩 방문하는 유한 그래프(Finite Graph)를 일컬어 오일러 경로(Eulerian Trail/Eulerian Path)라 부르며, 어려서부터 즐겨 하던 놀이 중 하나인 한붓그리기라고도 말한다. 글자 그대로 한 번도 붓을 떼지 않고 모든 간선을 한 번씩만 그릴 수 있는지를 의미한다. 그리고 마지막으로 가장 중요한 사항으로, 증명에 따르면 쾨니히스베르크의 다리는 모든 정점이 짝수개의 차수를 갖지 않으므로(심지어 짝수개의 차수를 갖는 정점은 하나도 없다) 오일러 경로가 아니다.
오일러는 어떤 그래프의 한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한번씩만 지나서 처음 출발점으로 되돌아오는 길을 가지려면 각 꼭짓점에 연결된 변의 개수가 모두 짝수여야 함을 증명했다.[4]
짝수여야 하는 이유는, 들어감-나감-들어감-나감-...(출발점에 한해서 나감-들어감-나감-들어감-...)의 구조가 반복되어 '나감'으로 끝나야 다른 점으로 이동할 수 있고 마지막 도착점이기도 한 출발점은 '들어감'으로 끝나야 그 점에서 멈출 수 있기 때문이다.
하지만 위의 문제의 경우 꼭짓점의 수가 홀수, 즉 들어감-나감-들어감으로 끝나기 때문에 어디서든지 시작해도 나갈 수 없다. 아무리 가짓수가 많아도 홀수라면 결국엔 '들어감'(출발점이라면 '나감')으로 끝나기 때문에 출발점으로 되돌아올 수 없게 된다. 따라서 오일러 경로가 성립되지 않는다. 단, 홀수점이 2개일 때는 그 두 개의 홀수점을 각각 출발점과 도착점으로 할 경우에 한해서 한붓그리기는 가능하며, 이러한 경로는 출발점으로 다시 되돌아오는 것이 아니므로 오일러 경로는 아니지만, 모든 변을 한 번씩만 지나기 때문에 오일러 경로에 준하다는 의미로 'Semi-Euler path'라고 한다.
이 문제의 해답을 찾기 위한 연구의 부산물로 그래프 이론이라는 수학의 한 분야가 생겨났다. 그래프 이론은 네트워크의 발달로 최근에 응용범위가 엄청나게 늘어난 분야이다. 어떤 그래프 이론 교과서든 쾨니히스베르크의 다리 문제는 역사적 배경과 함께 꼭 다루게 된다.
쾨니히스베르크의 다리 건너기는 1735년에 레온하르트 오일러가 가장 처음으로 답이 없다는 것을 증명하였고, 이후 이러한 유형의 문제를 체계적으로 연구하여 일반화시켰다. 이러한 오일러의 공로를 기리기 위해 위상기하학이나 전산학 분야에서는 이와 같은 문제를 오일러 경로(Euler path) 문제라고 표현한다.
만약 다리를 더 놓을 수 있다는 조건이 추가로 붙는다면,
이렇게 다리를 세 개 더 놓으면 해결 할 수 있다.# 그래프 이론으로는 설명할 때 모든 지점은 짝수 개의 연결로만 이루어져야 원래 자리로 돌아올 수 있으므로 두 개의 다리만 더 설치하면 된다. 그리고 '한붓그리기' ㅡ 꼭 원래 위치로 돌아올 필요없이 단순히 '한 번씩만 건너는' 데에만 한정한다면 아무 데나 다리를 하나만 더 놓아주거나, 다리 하나를 없애면 해결할수 있다.
4. 현재 칼리닌그라드에서 다리 한 번씩 건너기
배경이 된 장소의 현재 모습은 위성지도로 이렇게 생겼다.좀더 알아보기 쉬운 버전
북위 54도 42' 23.53'' 동경 20도 30'37.08
보다시피 배경이 된 칼리닌그라드의 다리는 5개밖에 남지 않았다. 7개 다리 중에서 2개는 동프로이센 공세 당시 이오시프 스탈린의 명령으로 소련군의 폭격이 진행되면서 소실되었고, 또 2개는 이후 고속도로로 대체 당해 원본 다리는 3개만이 남아있다. 아무튼 스탈린이 다리 2개를 폭격으로 날린 바람에 5개밖에 남지 않아 모든 다리를 한 번씩만 건너서 모두 건널 수 있는 방법이 생겼다. 어떤 방식으로든 해법이 나온 셈.
다만 여전히 임의의 위치에서 시작해서는 해결할 수 없고, 특정 위치에서만 가능하다. 상단의 위성사진 중앙에 보이는 섬 혹은 그 오른쪽에 있는 본토 2개를 말한다. 이를 도형으로 그리면 θ 형태가 되는데, 이 가로선의 양끝에 있는 두 꼭지점 모두 선이 3개 연결되어서 각각 출발점-도착점 역할을 하기 때문이다. 주파 방법은 당연히 5 혹은 그 반대인 2를 그리듯이 움직이는 것이다.
또한 한 번씩만 건너면서 출발점으로 돌아올 수 있는 방법은 없다. 상술한 두 꼭지점 모두 "나감-들어감-나감"으로 끝나기 때문에 절대로 출발점으로 돌아올 수 없기 때문이다. 따라서 한붓그리기 문제에서는 답이 있어도 오일러 경로 문제에서는 여전히 불가능하기 때문에 Semi-Euler path라고 부른다. 갈림길의 수가 홀수인 두 지점 가운데 하나에서 출발해서 반대편 지점에서 끝나는 방식이기 때문.
5. 기타 창작물에서
2007년 3월, 전국연합학력평가에 출제된 바 있다. 의도한 바인지 아닌지는 알 수 없지만 듣기를 살짝 놓치거나 이해하지 못한 학생은 그냥 그렸다.Q.E.D. 증명종료에서는 이 문제에 대해 '통과할 수 있다.'고 말하였다. 정답은 저~멀리 돌아가서 강의 원류를 넘어가기. 하지만 이는 실제로는 불가능한데, 그바르데이스크라는 곳에서 강이 두 개의 하류로 갈라지기 때문이다. 글로 설명하면 이해가 어려운데, 지도를 보면 한 눈에 이해할 수 있다.
즉, 실제로는 칼리닌그라드 북부를 포함한 땅덩어리가 하나의 거대한 섬[5]으로, 그바르데이스크[6]에서 갈라지는 데이마강을 넘어가지 않고서는 강의 원류를 돌아간다는 행위 자체가 아예 불가능하다. 프레골랴강이 흘러들어가는 비스툴라 석호를 발트해로 이어주는 물길이 13세기 말부터 15세기 말까지 단절되었던 적이 있기에 그 당시의 비스툴라곶을 건넌다면 가능했을지도 모르나, 그 때에는 이 문제는 물론이요 다리가 있는 쾨니히스베르크 시 자체가 세워지기도 전이었다.
네이버 웹툰 N의 등대 - 눈의 등대 편에서 등장한 적이 있다. 쾨니히스베르크 다리 건너기 문제와 똑같은 섬과 다리가 있는 곳에서 지도를 건네주며 '다리는 하루에 한 번씩 건널 수 있고 한 번 건넌 다리는 건널 수 없다'며 원본과 똑같은 문제를 제시하나, 원본과 똑같으면 당연히 풀 수 없으므로 '딱 한 번 두 명이 동시에, 건넜던 다리를 건너는 게 가능하다'란 추가 룰을 제시한다.[스포일러]
세미와 매직큐브 3화에서 세미 일행과 만난 레온하르트 오일러가 언급한다.
[1] Pregel. 현재 프레골랴(Преголя) 강[2] Kneiphof. 아래 그림에서 중앙에 다섯 개 다리와 연결된 섬. 러시아의 영토가 된 지금은 임마누엘 칸트의 이름을 따서 칸트 섬으로 개명되었다.[3] Lomse. 아래 그림에서 세 개 다리와 연결된 오른쪽 섬. 왼쪽의 크나이프호프에 비하면 매우 길고 커다란 섬이기에 다리가 놓인 부분만 보여주는 아래 그림에서는 대부분이 잘렸다. 동프로이센이 러시아 땅이 된 현재 이름은 10월 혁명을 기념하여 옥차브리스키 섬으로 변경되었다. 칼리닌그라드 스타디움이 들어서 있다.[4] 참고로 출발점으로 돌아올 필요가 없으면 홀수점이 두 개일 때도 성립한다.[5] 단, 2개로 나눠진 강으로 인해 육지와 나눠진 곳은 섬으로 보지 않기도 한다.[6] 동프로이센 시기 독일어 이름은 타피아우(Tapiau), 지금도 이 곳에 위치한 성인 타피아우 성에 그 이름이 남아있다.[스포일러] 다리는 지도와 눈에 보이는 게 다가 아니었고 일정 시간에만 밀물, 썰물 작용으로 드러났다가 사라지는 다리가 존재했다. 즉, 이 다리의 존재를 알고 이용한다면 굳이 번거로운 추가 룰을 쓸 이유가 없다.