한붓그리기

쾨니히스베르크의 다리 그래프. 이 그래프는 한붓그리기를 갖지 않는다.

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

정의

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

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

• ${\displaystyle G}$는 닫힌 한붓그리기를 가진다.
• ${\displaystyle G}$는 연결 그래프이며, ${\displaystyle G}$의 모든 꼭짓점의 차수는 짝수이다.

닫힌 한붓그리기를 갖는 그래프를 오일러 그래프(영어: Eulerian graph)라고 한다.

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

• ${\displaystyle G}$는 한붓그리기를 가진다.
• ${\displaystyle G}$는 연결 그래프이며, ${\displaystyle G}$의 홀수 차수 꼭짓점의 수는 0 또는 2이다.

만약 홀수 차수 꼭짓점이 2개 존재하는 경우, ${\displaystyle G}$의 한붓그리기는 이들 점들을 시작점·끝점으로 한다.

역사와 어원

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

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

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

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

외부 링크

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

같이 보기

• 해밀턴 경로