오일러 경로
위키백과 ― 우리 모두의 백과사전.
![]() |
이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
그래프 이론에서 오일러 경로(Euler path, Eulerian path)는 그래프의 모든 변을 단 한 번씩만 통과하는 경로를 뜻한다. 1736년 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 푼 것에서 유래되었다. 흔히 한붓 그리기 문제라고도 한다.
그 중에서 같은 꼭지점에서 시작해서 끝나는 오일러 경로를 오일러 회로(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 오일러 그래프라고 한다. 오일러는 어떠한 그래프가 오일러 그래프가 되기 위한 필요충분조건은 모든 꼭지점의 차수가 짝수이어야 한다는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(즉, 시작 꼭지점과 끝 꼭지점이 다른 경로)의 필요충분조건은 정확히 두 개의 꼭지점만이 홀수의 차수를 지녀야한다는 것이다. 이와 같은 조건은 다중 그래프에서도 유효하다.
[편집] 오일러 회로의 속성
- 무향 그래프의 모든 꼭지점의 차수가 짝수라면 오일러 회로가 존재한다.
- 유향 그래프가 오일러 회로를 가지기 위해선 각각의 꼭지점의 내차수와 외차수가 같아야한다.
- 무향 그래프의 오일러 회로가 아닌 오일러 경로는 그래프에 단 두 개의 꼭지점만이 홀수의 차수를 가지고 있어야 존재한다.