한붓그리기 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Königsberg_graph.svg|섬네일|165px|쾨니히스베르크의 다리 그래프. 이 그래프는 한붓그리기를 갖지 않는다.]]

[[그래프 이론]]에서 '''한붓그리기''' 또는 '''오일러 트레일'''({{llang|en|Eulerian trail}})은 [[그래프]]의 모든 변을 단 한 번씩만 통과하는 [[그래프 이론 용어|트레일]]이다.

== 정의 ==
(단순) 그래프 <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}})라고 한다.

(단순) 유한 [[그래프]] <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>G</math>는 한붓그리기를 가진다.
* <math>G</math>는 연결 그래프이며, <math>G</math>의 홀수 차수 꼭짓점의 수는 0 또는 2이다.
만약 홀수 차수 꼭짓점이 2개 존재하는 경우, <math>G</math>의 한붓그리기는 이들 점들을 시작점·끝점으로 한다.

== 역사와 어원 ==
[[파일:Konigsberg_bridges.png|섬네일|right|[[쾨니히스베르크]]의 [[프레골랴강]]을 건너는 7개의 다리]]
{{본문|쾨니히스베르크의 다리 문제}}
1736년에 [[레온하르트 오일러]]가 [[쾨니히스베르크의 다리 문제]]를 풀기 위하여 도입하였다. 이는 [[그래프 이론]]의 시초로 여겨진다.

"한붓그리기"라는 이름은 그래프를 붓으로 종이 위에 그리는 것에 빗댄 것이다. 그래프를 한붓그리기를 따라 그리게 되면 붓을 종이에서 떼지 않고, 이미 그린 변을 덧칠할 필요 없이 그릴 수 있다.

== 외부 링크 ==
{{위키공용분류}}
* {{언어링크|en}} [https://web.archive.org/web/20120204044703/http://mathforum.org/kb/message.jspa?messageID=3648262&tstart=135 Discussion of early mentions of Fleury's algorithm]

== 같이 보기 ==
* [[해밀턴 경로]]

[[분류:그래프 이론]]
[[분류:사람 이름을 딴 낱말]]
[[분류:레온하르트 오일러]]