오일러 경로와 회로

정점들과 각각의 정점들을 잇는 간선들이 존재한다고 하자.(간선이 연결되지 않은 정점은 고려하지 않는다, 모든 정점에는 적어도 하나 이상의 간선이 연결되어있어야 한다.)

경로는 한 정점에서 출발해 다른 정점에 도달하거나 다시 출발 정점으로 돌아오는 방법이다.

회로는 한 정점에서 출발해 다시 그 정점으로 돌아오는 방법이다.

오일러 경로와 회로는 모든 간선을 한번씩 방문하면서 원하는 정점까지 이동할 수 있는지에 관한 문제이다.

차수는 한 정점에서 다른 정점으로 연결된 간선의 갯수 이다.






그렇다면, 오일러 회로를 존재하게 하는 필요충분 조건은 무엇있까? 

모든 정점의 차수가 짝수 <->오일러 회로가 존재.

모든 정점의 차수가 짝수인 상황을 가정해보자.

시작점이 아닌 차수가 짝수인 정점은 그 정점과 연결된 간선을 모두 한번씩 지나가면 필연적으로 그 정점에서 끝을 맺을 수가 없다. 들어온 숫자 만큼 나가기 때문이다. 따라서 이용할수 있는 마지막 간선을 타고 또다른 정점에 도달하고. 또다른 정점도 아무리 많은 간선을 소모했다 하더라도 마지막 하나는 다른 정점으로 이어주게 된다.

따라서 어떤 간선을 먼저 이용하던간에 궁극적으로 다시 시작 정점에 돌아올 수 밖에 없다. 시작정점도 간선을 통해 나간 수만큼 들어와야 하기 때문이다.

따라서 모든 정점의 차수가 짝수일때는 오일러 회로가 존재하며, 그 어떤 정점도 회로의 시작점이 될 수 있다.

반대로 차수가 홀수인 정점이 존재한다고 해보자.

그렇다면, 모든 간선을 다 한번씩 이용 못하는 경우도 생길 수 있겠다. 또한 모든 간선을 반드시 한번씩 이용하는 경우를 가정했을때도 결국 중간에 껴있는 차수가 홀수인 정점에서 더이상 나아갈 간선이 없이 막혀버린다.

따라서 차수가 홀수인 정점이 존재할때는 반드시 오일러 회로는 존재하지 않는다.





그렇다면, 오일러 경로가 가능해지는 필요충분조건은 무엇일까?

출발정점과 도착정점의 차수가 홀수이며 나머지 정점의 차수가 짝수 or 모든 차수가 짝수 <->오일러 경로가 존재.

위의 증명과 같은 논리로 증명하는데

출발 정점과 도착 정점의 차수만 홀수인 경우를 가정하자.

모든 간선을 한번씩 소모해가면서 앞으로 진행해갈때 출발 정점은 필연적으로 마지막으로 사용한 간선은 다른 정점으로 이동하는데 사용하게되며 다시 출발 정점으로 돌아올 간선은 남지 않게 된다.

도착정점은 연결된 마지막 간선을 반드시 도착정점에 도달하는데 사용하게 된다.

나머지 정점들은 모두 차수가 짝수이므로 반드시 연결된 마지막 간선이 다른 정점으로 나아갈 수 있게 해준다.

만약 두 정점 이외에 차수가 홀수인 점이 존재한다면 반드시 그 정점에서 진행이 불가하다.

또한 한 정점만 홀수라면 모든 간선을 사용하는게 불가하다. 사실 에초에 한 정점만 홀수개의 간선을 가지는 것은 불가능 하다. 간선이 하나 추가될때마다 두개의 정점의 차수가 하나씩 높아지기 때문이다.

모든 정점의 차수가 짝수라면 위에서 말한대로 오일러 회로가 존재하는 필요충분 조건이기 때문에 오일러 경로 또한 반드시 존재한다.