한 붓 그리기 가능한 경우

정보 올림피아드 필기에 한 붓 그리기 문제는 매년 출제되는 단골 문제 입니다. 따라서 한 붓 그리기가 언제 가능한지 꼭 기억하고 있어야 합니다. 한 붓 그리기는 오일러 경로(Euler trail)라고도 합니다. 한 붓 그리기는 이미 1736년에 오일러가 증명 했습니다. 한 붓 그리기가 가능한 도형에 대해 알아보겠습니다.

꼭지점의 차수가 모두 짝수 일때

차수란 꼭지점에 인접한 선분이 몇 개인지를 나타냅니다.

위 그림처럼 모든 쪽지점의 차수가 짝수일 때 어느 지점으로 시작해도 다시 출발점으로 돌아오는 한 붓 그리기가 가능합니다.

차수가 모두 짝수인 경우 어느 지점에서 시작해도 한 붓 그리기가 가능하고 출발점으로 돌아옵니다.

꼭지점의 홀수 차수가 2개 일 때

먼저 꼭지점의 홀수 차수가 1개인 경우는 없습니다. 최소 2개인 경우가 있는데 이 경우 홀수점에서 한 붓 그리기를 하면 다른 홀수점에서 한 붓 그리기를 완료 할 수 있습니다.

위의 두 도형을 보면 꼭지점을 나타내는 빨간 원은 3개의 선분이 만나 홀수점이고, 주황색은 짝수의 선분이 만나는 것을 알 수 있습니다. 두 도형 모두 차수가 홀수인 꼭지점이 2개입니다. 이 경우 홀수점에서 시작하면 한 붓 그리기가 가능합니다. 직접 한 붓 그리기를 해보면 차수가 짝수인 꼭지점에서 시작하면 그릴 수 없고, 홀수인 꼭지점에서 시작하면 다른 홀수점에서 끝나는 한 붓 그리기가 가능한 것을 알 수 있습니다.

홀수 차수가 2개인 경우 한 붓 그리기가 가능하고, 홀수 차수에서 시작하면 다른 홀수 차수에서 끝납니다.

꼭지점의 홀수 차수가 2개보다 큰 경우

홀수의 차수가 2개보다 큰 경우 한 붓 그리기를 할 수 없습니다.