오일러 서킷 (Eulerian circuit)

오일러 서킷(Eulerian circuit)

: 그래프의 모든 간선을 정확히 한번씩 지나서 시작점으로 돌아오는 경로.

 

오일러 경로(Eulerian path)

: 그래프의 모든 간선을 정확히 한번씩 지나는 경로. 시작점과 도착점이 다르다.

 

무향 그래프에서 오일러 서킷을 찾으려면?

먼저 오일러 서킷의 존재 여부를 확인한다.

1. 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우는 오일러 서킷이 존재할 수 없다.

그래프의 정점이 둘 이상의 컴포넌트로 쪼개져 있어도, 간선들이 한 컴포넌트에 있다면 오일러 서킷은 존재한다.

그래프의 모든 '간선'을 지나 시작점으로 되돌아오기만 하면 되기 때문.

2. 도착점에 인접한 모든 간선은 이미 지나온 상황이어야한다.

 

3. 도착점에 인접한 간선의 수는 항상 짝수이다. 시작점에서 나가는 것으로 시작했으니, 들어온 뒤 다시 나갈 수 없다면 지금까지 사용한 간선의 수는 항상 짝수여야 한다.

시작점과 도착점이 같은 정점이기때문에 시작점에서 나가는 간선이 있다면 들어오는 간선또한 존재한다.

도착점에 인접한 간선의 수가 4이상인 경우(n>=4)도 마찬가지이다. 나가는 간선과 들어오는 간선이 한 쌍이 되어 해당 정점은 총 n/2+1번 방문하는 상황이 된다.

 -> 그래프 모든 정점은 인접한 간선의 수가 짝수개이다.

시작점과 도착점이 같다는 것은 사이클이라는 뜻이고, 사이클인 경우 그래프 아무 정점이 시작점이 되어도 같은 서킷을 만들 수 있다.

 

한 정점에 인접한 간선의 수를 해당 정점의 차수(degree)라고 부른다.

차수가 짝수인 점을 짝수점, 홀수인 점을 홀수점이라 하자.

 

그래프 모든 정점이 짝수점이면서, 간선들이 하나의 컴포넌트에 포함된다면 항상 오일러 서킷을 만들 수 있다.

그러면서 동시에 모든 정점이 출발점(도착점)이 될 수 있다.(사이클)

 

 

오일러 경로의 경우(출발점과 도착점이 다를 때)

출발점과 도착점이 다르므로,

출발점은 해당 정점에서 나가는 나가는 액션이 가장 먼저 수행되고, 다시 들어오더라도 나가야만한다.

그러므로 출발점은 항상 홀주점이어야한다. 나가는 간선이 항상 들어오는 간선+1개이기 때문이다.

 

반대로 도착점은 다른 어떤 정점으로부터 도착점으로 들어오는 간선으로 인해 방문된다. 다른 간선으로 인해 나가더라도 마지막 정점이 되어야하기 때문에 들어와야만한다.

그러므로 도착점은 항상 홀수점이어야한다. 들어오는 간선이 항상 나가는 간선+1개이기 때문이다.

 

나머지 정점들은 항상 짝수점이어야한다. 들어오는 횟수만큼 나가야하기 때문이다.

이렇게 되면 오일러 서킷과는 다르게 오일러 경로는 출발점과 도착점이 정해져있어야한다. 출발점이 달라지면 경로가 달라지거나(역방향) 경로를 만들 수 없게된다.