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

483 바이트 추가됨 ,  6년 전
편집 요약 없음
[[파일:Königsberg_graph.svg|thumb|165px|쾨니히스베르크의 다리 그래프. 이 그래프는 오일러 [[그래프트레일을 이론갖지 용어사전#용어|회로]]를 가지고 있지 않다않는다.]]
 
[[그래프 이론]]에서, '''오일러 경로'''(Euler{{llang|en|Eulerian path,}}) Eulerian또는 path)'''한붓그리기'''는 [[그래프 이론]]에서 [[그래프]]의 모든 [[그래프 이론 용어사전#용어|변]]을 단 한 번씩만 통과하는 [[그래프 이론 용어사전#용어|경로트레일]]를 뜻한다. [[1736년]] [[레온하르트 오일러]]가 [[쾨니히스베르크의 다리 문제]]를 푼 것에서 유래되었다. 흔히 '''한붓그리기''' 문제라고도 한다이다.
 
== 정의 ==
그 중에서 같은 꼭지점에서 시작해서 끝나는 오일러 경로를 '''오일러 회로'''(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 '''오일러 그래프'''라고 한다. 오일러는 그래프가 오일러 회로를 가질 필요충분조건은
(단순) 그래프 <math>G</math> 위의 '''오일러 트레일''' 또는 '''한붓그리기'''는 그래프의 모든 변을 포함하는 [[그래프 이론 용어사전|트레일]]이다. (정의에 따라, 트레일은 변을 중복해서 거칠 수 없다.) '''닫힌 오일러 트레일'''은 시작점과 끝점이 같은 오일러 트레일이다. 일부 저자들은 닫힌 트레일을 '''회로'''({{llang|en|circuit}})라고 부르며, 이 경우 닫힌 오일러 트레일은 '''오일러 회로'''({{llang|en|Eulerian circuit}})가 된다.
* 그 그래프가 연결된 그래프이고,
 
* 모든 꼭지점의 [[그래프 이론 용어사전#용어|차수]]가 짝수이어야 한다.
(단순) 유한 [[그래프]] <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
라는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(즉, 시작 꼭짓점과 끝 꼭짓점이 다른 경로)가 있을 필요충분조건은
* <math>G</math>는 닫힌 오일러 트레일을 가진다.
* '정확히 두 개의 꼭지점만이 홀수의 차수를 가지고
* <math>G</math>는 연결 그래프이며, <math>G</math>의 모든 꼭짓점의 차수는 짝수이다.
* 그 그래프가 [[그래프 이론 용어사전#용어|연결]]되어 있다.'
닫힌 오일러 트레일을 갖는 그래프를 '''오일러 그래프'''({{llang|en|Eulerian graph}})라고 한다.
라는 것이다. 이와 같은 조건은 [[그래프#정의|다중 그래프]]에서도 유효하다.
 
* 그리고 홀수차수가 2개인 그래프는 한 홀수점에서 출발하여 다른 홀수점이 종착점이 되도록 그리면 된다.
(단순) 유한 [[그래프]] <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>G</math>는 오일러 트레일을 가진다.
* <math>G</math>는 연결 그래프이며, <math>G</math>의 홀수 차수 꼭짓점의 수는 0 또는 2이다.
만약 홀수 차수 꼭짓점이 2개 존재하는 경우, <math>G</math>의 오일러 트레일은 이들 점들을 시작점·끝점으로 한다.
 
== 역사 ==
[[File:Konigsberg_bridges.png|thumb|right|[[쾨니히스베르크]]의 [[프레골랴 강]]을 건너는 7개의 다리]]
{{본문|쾨니히스베르크의 다리 문제}}
1736년에 [[레온하르트 오일러]]가 [[쾨니히스베르크의 다리 문제]]를 풀기 위하여 도입하였다.
 
== 바깥 고리 ==
{{Commons category|Eulerian paths}}
* {{언어고리|en}} [http://mathforum.org/kb/message.jspa?messageID=3648262&tstart=135 Discussion of early mentions of Fleury's algorithm]
 
{{토막글|수학}}
 
[[분류:그래프 이론]]