쾨니히스베르크의 일곱 개의 다리 문제와 오일러 경로(Eulerian path)

쾨니히스베르크의 일곱 개의 다리 문제와 오일러 경로(Eulerian path)

러시아 칼리닌그라드(현재의)에 위치한 쾨니히스베르크라는 옛 도시의 특정 구조를 기반으로 하는 수학 문제입니다. 이 도시는 프레겔(Pregel) 강 위에 네 개의 주요 지구가 있었고 이 지구들을 연결하는 일곱 개의 다리가 있었습니다.
https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

 

문제의 내용

일곱개의 다리를 한 번씩만 건너면서 도시를 통과하는 산책로를 고안하는것
 
스위스 수학자 레온하르트 오일러(Euler)가 이 문제를 처음으로 수학적으로 분석했고 이 과정에서 그래프 이론(Graph Theory)의 기초가 마련되었습니다.

 
도시를 그래프로 단순화
각 지구를 정점(vertices)으로 다리를 간선(edge)으로 표현하여 도시를 그래프로 나타냄

 
오일러 경로의 조건
오일러는 그래프의 모든 간선을 한 번씩만 지나는 경로 즉 오일러 경로(Eulerian Path)가 존재하려면 특정 조건을 만족해야 함을 발견했습니다. 그래프에 오일러 경로가 존재하려면 0개 또는 2개의 정점이 홀수 차수를 가져야 합니다(정점의 차수는 정점에 인접한 모서리의 수를 의미)
 
쾨니히스베르크의 그래프에서는 모든 정점이 홀수 차수를 가지고 있었기 때문에 이 문제에는 오일러 경로가 존재하지 않으며 다리를 한 번씩만 건너는 방법은 불가능하다는것을 증명하였습니다.
 
오일러 경로
그래프 이론에서 오일러 경로는 유한 그래프의 모든 에지를 한 번씩만 방문하는 경로(정점을 다시 방문하는것을 허용)
https://en.wikipedia.org/wiki/Eulerian_path
아래 예시에서 두개의 그래프 모두 2개 이상의 홀수 차수 정점(주황색)을 갖습니다. 따라서 오일러 경로가 존재하지않습니다.