한붓그리기

쾨니히스베르크의 다리 그래프. 이 그래프는 오일러 트레일을 갖지 않는다.

그래프 이론에서, 오일러 트레일(영어: Eulerian trail) 또는 한붓그리기는 그래프 이론에서 그래프의 모든 변을 단 한 번씩만 통과하는 트레일이다.

정의

(단순) 그래프 $G$ 위의 오일러 트레일 또는 한붓그리기는 그래프의 모든 변을 포함하는 트레일이다. (정의에 따라, 트레일은 변을 중복해서 거칠 수 없다.) 닫힌 오일러 트레일은 시작점과 끝점이 같은 오일러 트레일이다. 일부 저자들은 닫힌 트레일을 회로(영어: circuit)라고 부르며, 이 경우 닫힌 오일러 트레일은 오일러 회로(영어: Eulerian circuit)가 된다.

(단순) 유한 그래프 $G$에 대하여, 다음 두 조건이 서로 동치이다.

• $G$는 닫힌 오일러 트레일을 가진다.
• $G$는 연결 그래프이며, $G$의 모든 꼭짓점의 차수는 짝수이다.

닫힌 오일러 트레일을 갖는 그래프를 오일러 그래프(영어: Eulerian graph)라고 한다.

(단순) 유한 그래프 $G$에 대하여, 다음 두 조건이 서로 동치이다.

• $G$는 오일러 트레일을 가진다.
• $G$는 연결 그래프이며, $G$의 홀수 차수 꼭짓점의 수는 0 또는 2이다.

만약 홀수 차수 꼭짓점이 2개 존재하는 경우, $G$의 오일러 트레일은 이들 점들을 시작점·끝점으로 한다.

역사

쾨니히스베르크의 프레골랴 강을 건너는 7개의 다리

 이 부분의 본문은 쾨니히스베르크의 다리 문제입니다.

1736년에 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 풀기 위하여 도입하였다. 이는 그래프 이론의 시초로 여겨진다.

바깥 고리

• (영어) Discussion of early mentions of Fleury's algorithm

같이 보기

• 해밀턴 경로