한붓그리기 조건에 대해서(오일러 서킷, 오일러 트레일)

한 붓 그리기에 대한 공식을 명확히 알 필요가 있을 것 같아 정리해둘려고 한다. 

한 붓 그리기란 그래프의 어느 한 점에서 시작하여 모든 간선들을 한 번씩만 지나가는 

경우를 말한다. 

이 것에 대한 조건은 일단 두 가지로 나뉜다. 

1) 모든 정점이 가지는 간선이 다 짝수 개 일 때

2) 두 정점만 간선이 홀 수개를 가질 때 

이렇게 가능하다고 한다. 

한붓그리기의 경로를 뽑아내기 위해서는 dfs의 마지막 부분에 출력을 넣어주면 된다. 

뒤에서부터 출력하면 가능하다. 이 부분은 제대로 이해를 못 해서 직접 손으로 그려봐야겠다

특징

- 오일러 서킷

1) 모든 정점의 간선의 개수는 짝수여야 함(무향)

2) 들어오고 나가는 것이 있어야 됨(유향)

- 오일러 트레일

시작점과 끝점의 간선이 홀수개여야 함(무향)

(방향)

시작점 : 들어오는 간선이 나가는 것보다 하나 더 적어야 함

끝 점 : 들어오는 간선이 나가는 것보다 하나 많아야 한다.