쾨니히스베르크 다리 문제

그림처럼 프로이센의 쾨니히스베르크(오늘날 러시아 칼리닌그라드)에는 강이 있고 강으로 둘러싸인 섬이 하나 있다. 섬을 잇는 다리가 7개가 있는데 사람들 가운데 운동이나 산책을 하면서 이 다리들을 모두 한 번씩만 건너서 출발한 곳으로 다시 돌아오려고 하는 이들이 있었다. 아무도 답을 찾지 못하고 있던 문제를 오일러가 각 지점을 점으로 다리는 변으로 생각하는 그래프를 고안하여 그럴 수 없다는 것을 밝혀냈다.(1735년) 위키디피아로

오일러는 어떤 그래프에  한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한번씩만 지나서 처음 출발점으로 되돌아오는 길을 가지려면 각 꼭짓점에 연결된 변의 개수가 모두 짝수이어야 함을 증명했다.

오늘날 이산수학에서는 위 그림을 아래와 같이 간단하게 그래프로 나타낸다.

그래프 이론에서 오일러 경로(Euler path, Eulerian path)는 그래프의 모든 변을 단 한 번씩만 통과하는 경로를 뜻한다. 흔히 한붓그리기라고도 한다. 그 가운데 같은 꼭짓점에서 시작해서 끝나는 오일러 경로를 오일러 회로(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 오일러 그래프라고 한다. 각 꼭짓점에 연결된 변의 개수를 차수라고 한다.

오일러는 그래프가 오일러 회로를 가질 필요충분조건은

그래프가 연결된 그래프이고, 모든 꼭짓점의 차수가 짝수이어야 한다.

라는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(시작과 끝 꼭짓점이 다른 경로)가 있을 필요충분조건은

'정확히 두 개의 꼭짓점만이 홀수의 차수를 가지고 그래프가 연결되어 있다.'

라는 것이다. 이와 같은 조건은 다중 그래프에서도 마찬가지다. 홀수 점이 2개인 그래프는 한 홀수 점에서 출발하여 다른 홀수점이 끝나도록 그리면 된다.

해밀턴 경로와 회로는 아래를 참고하자.

https://suhak.tistory.com/122

그래프와 행렬