철학자 칸트가 일생을 보냈던 곳, 수학사에서 유명한 문제 "쾨니히스베르크의 일곱 개의 다리(Seven Bridges of Königsberg)"

수학사에서 아주 유명한 문제

"쾨니히스베르크의 일곱 개의 다리(Seven Bridges of Königsberg)" 

 

쾨니히스베르크

철학자  임마누엘 칸트(Immanuel Kant)가 일생을 보냈던 곳

 1724년 쾨니히스베르크 쾨니히스베르크(Königsberg) 출생,  1804년 그곳에서 생을 마감

(현재 러시아의 칼리닌그라드)
그는 일생을 이 도시에서 보냈고,

평생 한 번도 고향을 떠난 적이 없을 정도로 엄청나게 규칙적인 생활로 유명

매일 같은 시간에 산책을 나갔기 때문에,
“쾨니히스베르크 시민들이 칸트의 산책 시간으로 시계를 맞췄다”는 말까지 있을 정도

 

"쾨니히스베르크의 일곱 개의 다리"

(Seven Bridges of Königsberg)

 

 문제의 배경
18세기 프로이센 왕국의 도시 쾨니히스베르크(Königsberg, 현재 러시아의 칼리닌그라드)

프레겔(Pregel) 강이 흐르고, 강을 가로지르는 7개의 다리가 있었다.

도시에는 강에 의해 나눠진 네 구역이 있었고, 사람들은 이런 의문을 가졌다.

"모든 다리를 한 번씩만 건너면서, 시작한 지점으로 돌아올 수 있을까?"

이 문제는 결국 그래프 이론(Graph Theory)의 탄생으로 이어졌고,

레온하르트 오일러(Euler)가 이를 다루면서

오일러 경로(Eulerian Path) 개념이 탄생

 오일러의 해결
오일러는 이 문제를 지리적/물리적 문제로 보지 않고, 추상화

도시의 각 구역을 점(정점, vertex)

다리를 선(간선, edge)으로 나타낸 그래프로


모든 정점의 차수(즉, 해당 정점과 연결된 간선의 수)가 짝수

오일러 회로(Eulerian circuit, 시작점으로 돌아오는 경로)가 존재
두 개의 정점만 홀수 차수일 때

오일러 경로(Eulerian path, 끝점이 다를 수 있는 경로)가 존재

쾨니히스베르크 문제는 네 정점 중 모두 홀수 차수였기 때문에,

 해당 조건을 만족하지 않음 ⇒ 불가능!

의의

 

오일러가 이 문제를 통해 그래프 이론과 위상수학의 기초를 마련