내용으로 건너뛰기

"한붓그리기"의 두 판 사이의 차이

137 바이트 추가됨 ,  9년 전
그래프 이론 용어사전과 링크
잔글 (r2.7.1) (로봇이 더함: et:Euleri graaf)
(그래프 이론 용어사전과 링크)
[[파일:konigsburg_graph.svg|thumb|165px|쾨니히스베르크의 다리 그래프. 이 그래프는 오일러 회로를[[그래프 이론 용어사전#용어|회로]]를 가지고 있지 않다.]]
 
[[그래프 이론]]에서 '''오일러 경로'''(Euler path, Eulerian path)는 [[그래프]]의 모든 [[그래프 이론 용어사전#용어|변]]을 단 한 번씩만 통과하는 경로를[[그래프 이론 용어사전#용어|경로]]를 뜻한다. [[1736년]] [[레온하르트 오일러]]가 [[쾨니히스베르크의 다리 문제]]를 푼 것에서 유래되었다. 흔히 '''한붓그리기''' 문제라고도 한다.
 
그 중에서 같은 꼭짓점에서꼭지점에서 시작해서 끝나는 오일러 경로를 '''오일러 회로'''(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 '''오일러 그래프'''라고 한다. 오일러는 그래프가 오일러 회로를 가질 필요충분조건은
* 그 그래프가 연결된 그래프이고,
* 모든 꼭짓점의꼭지점의 [[그래프 이론 용어사전#용어|차수]]가 짝수이어야 한다.
라는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(즉, 시작 꼭짓점과 끝 꼭짓점이 다른 경로)가 있을 필요충분조건은
* '정확히 두 개의 꼭지점만이 홀수의 차수를 가지고
* 그 그래프가 연결되어[[그래프 이론 용어사전#용어|연결]]되어 있다.'
라는 것이다. 이와 같은 조건은 [[그래프#정의|다중 그래프]]에서도 유효하다.
* 그리고 홀수차수가 2개인 그래프는 한 홀수점에서 출발하여 다른 홀수점이 종착점이 되도록 그리면 된다.

편집

70