-
오일러 회로는 그래프의 모든 간선을 방문하고 시작점과 끝점이 같은 회로를 말한다. 우리에게는 연필로 모든 간선을 칠하고 다시 돌아오는 것으로 친숙하다. 별표그릴때를 생각해보면.
이 회로를 만들기 위한 조건은 각 정점들마다 나가고 들어오는 간선의 수가 같아야 한다(무방향의 그래프는 정점과 연결된 간선의 수가 짝수개여야 한다)
정말 간단히 생각하면 된다.
어떤 정점의 나가는 간선의 수가 들어오는 간선의 수보다 적다면 그 정점으로 들어오는 간선들은 아직 방문하지 못한채 그 정점에서 나가지 못하게 된다.
위의 그림에서 정점은 2개의 나가는 간선과 3개의 들어오는 간선이 있다. 검은색 간선은 이미 방문 한 것이고 파란색 간선은 아직 방문하지 않는 것이다. 현재 위치는 정점 3인데 여기서 더이상 어느 곳으로 나갈 수 없다. 나가지 못하므로 다시 3으로 들어오는 간선을 방문 할수도 없다.
만약 더이상 방문할 간선이 없다면 오일러 회로가 성립한 것이나 파란색 간선이 남아있으므로 오일러 회로를 만들 수 없다.
위와 같은 정점이 그래프에 하나라도 있으면 오일러 회로는 만들수가 없다
모든 정점이 나가고 들어오는 간선의 수가 같아야만 오일러 회로가 성립하게 된다.
회로 존재의 유무를 찾는것은 쉬운데 회로를 찾는것은 조금 난감하다.
저자는 재귀함수를 이용해서 간단히 풀어버렸는데.. 나는 재귀함수 호출순서가 뭔가 문제가 있지 않을까 생각한다.... 물론 내가 틀렸을것 같은데... 이런게 아무래도 실력인가;
