백과

[1] 18세기에 오일러가 준 그래프의 한붓그리기에 관한 다음의 정리. 연결은 무향 그래프 G에, 모든 가지를 꼭 한번씩 지나는 폐로(경로 참고)가 존재하기 위한 필요충분조건은, G의 모든 노드의 차수가 짝수인 것이다. 이와 같은 폐로를 오일러 폐로(Euler cycle)라 하고, 오일러 폐로를 가지는 그래프를 오일러 그래프(Eulerian graph)라고 한다(그림).

오일러의 정리

ⓒ 한국사전연구사 | 저작권자의 허가 없이 사용할 수 없습니다.

이 정리에서 다음과 같은 것을 알 수 있다. 그래프 G가 한붓그리기가 되기 위한(즉, 모든 가지를 꼭 한번씩 지나는 길이 존재하기 위한) 필요충분조건은 2노드를 제외한 다른 모든 노드의 차수가 짝수인 것이다. 오일러의 정리는 케니히스베르그의 다리 문제에 대한 오일러의 연구에서 얻어진 것으로서, 그래프 아론의 기원으로 되어 있다. 〈참조어〉 오일러 그래프, 오일러 폐로

[2] 초등정수론에 있어서의 정리에 대해서는 페르마의 정리.