한붓 그리기란?
그래프의 어느 한점에서 시작하여 모든 간선들을 한번씩만 지나가는 경우이다. 정점은 여러번 지나도 상관없다.
오일러 경로
오일러 경로(Eulerian Trail)란 그래프에 존재하는 모든 간선들을 정확히 1번씩만 방문하는 연속된 경로이다. 이때 경로의 시작점과 끝나는 점이 같다면 이를 오일러 서킷(Eulerian Circuit)이라 한다.
위의 그림은 오일러 서킷의 대표적 그래프인 별 모양 그래프이다. 어떤 정점에서 시작하더라도 모두 간선을 1번씩만 지나 다시 시작점으로 돌아올 수 있다. 오일러 서킷의 특징은 무향 그래프에서 모든 정점의 차수가 짝수이다. 모든 정점에서 들어오는 간선과 나가는 간선이 짝을 이루기 때문에 2의 배수꼴로 차수가 표현된다.
위의 그림은 오일러 경로는 존재하지만 오일러 서킷은 존재하지 않는 예이다.
오일러 경로 존재 여부의 판단은 무향 그래프일 경우에
- 모든 정점의 차수가 짝수이면 오일러 서킷이 존재하는 것이다.
- 홀수 차수를 가진 정점이 2개(시작점, 끝점)라면 오일러 경로를 가진다.
