오일러 서킷, 경로(Eulerian circuit, eulerian path)

 * 오일러 서킷

그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 시작점으로 돌아오기 때문에 오일러 서킷은 사이클임을 알 수 있다.

 * 오일러 경로

그래프의 모든 간선을 정확히 한 번씩 지나는 경로를 말한다. 시작점과 도착점이 다를뿐(오일러 경로는 사이클이 아니다), 나머지 속성은 오일러 서킷과 같다.

 * 오일러 서킷/경로 존재 조건

배제의 방식으로 접근한다. 반대로 오일러 서킷이 존재할 수 없는 그래프를 파악하면 된다.

u = v의 경우는 오일러 서킷이고, u != v의 경우는 오일러 경로를 말한다.

1. Graph components가 두 개 이상

Components가 두 개 이상이면 한 번의 연산(사이클)이 절대로 모든 간선을 지날 수 없다.

2-1. (양/무방향 그래프) u에서 v로 가는 오일러 서킷을 찾고자 할 때

2-1-1. u = v

v에 인접한 간선의 수는 항상 짝수여야 한다. u에서 나가는 것으로 시작한다면 들어온 뒤 다시 나갈 수가 없어야 하기 때문이다.

2-1-2. u != v

v에 인접한 간선의 수는 항상 홀수여야 한다. v에 들어가서 나올 수 없다는 소리는 마지막으로 지나는 간선이 v와 연결되어 있다는 소리이며 v를 통해 다른 정점을 지나기 위해선 나가는 간선과 들어오는 간선이 짝으로 구성되어 있어야 하기 때문이다.

2-2. (방향 그래프) u에서 v로 가는 오일러 서킷을 찾고자 할 때

2-2-1. u = v

진입 차수과 진출 차수의 수가 같다. 즉, indegree[v] = outdegree[v]이어야 오일러 서킷이 가능하다. 이는 나가는 간선과 들어오는 간선이 같아야 사이클이 생기며 시작점으로 돌아올 수 있기 때문이다.

2-2-2. u != v

시작점과 도착점(u와 v)을 제외한 모든 정점은 반드시 진입 차수과 진출 차수의 값이 같아야만 한다. 또한 시작점 u는 진출 간선이 진입 간선보다 정확히 하나 더 많아야 하며, 도착점 v는 진입 간선이 진출 간선보다 정확히 하나 더 많아야 한다.

 * 오일러 서킷과 경로

  위 조건을 만족하는 오일러 서킷은 모든 정점이 짝수이기 때문에 어느 정점에서 시작하든지 상관이 없다(사이클 속성). 하지만 오일러 경로의 경우에는 시작점과 도착점이 정해져 있다. u와 v에 대해 오일러 경로가 존재할 때, 만약 무방향이라면 u에서 시작하든 v에 시작하든 상관은 없다. 하지만 방향 그래프라면 u와 v에서 진출 차수가 하나 더 많은 정점을 반드시 시작점이 되어야 한다. 위 조건에 따르면 도착점은 반드시 진입 간선이 하나 더 많아야 한다.

 * 구현

  오일러 서킷과 오일러 경로는 모두 DFS로 구현할 수 있다. 모든 간선을 지나야하는 것을 생각해보자. 또한 오일러 서킷은 사이클이기 때문에 부분 사이클끼리 합칠 수 있다. 가령 A->B->C->A로 가는 사이클과 B->D->E->B 사이클이 있다고 가정하자. 그렇다면 두 번째 B로 돌아오는 사이클과 첫 번째 A로 돌아오는 사이클을 끼워 넣어서 부분 사이클끼리 합칠 수 있다. 합치면 다음과 같다.

A->[B->D->E->B]->C->A

  따라서 DFS 재귀에서는 마지막에 방문 정점 번호를 삽입함으로써 순서를 알 수 있다. 단 방문 정점은 거꾸로 들어가기 때문에 반드시 거꾸로 읽어줘야 한다.

  그렇다면 오일러 경로는 어떨까? 오일러 경로는 무방향이든 방향이든 도착점과 시작점을 u와 v라고 할 때, u와 v로 잇는 간선을 만들어주면 필연적으로 오일러 회로를 구할 수 있게 된다. 따라서 시작점과 도착점을 잇는 간선이 있다고 가정한 상태에서 오일러 회로를 구하면 그것이 곧 오일러 경로가 된다.

 * 오일러 서킷 및 경로 존재 여부

 DFS 돌리기 전에 반드시 오일러 서킷과 경로가 존재하는지 반드시 확인해야 한다. 위에서 설명한 2번에 해당하는 모든 조건을 확인한다. 1번 조건은 나중에 모든 간선을 지났는지 확인이 가능하기 때문에 2번부터 확인한다.

코드 : 

for (i = 0; i < 26; i++) {
	int delta = outd[i] - ind[i];
	if (delta < -1 || 1 < delta) invalid = 1;
	if (delta == 1) p++;
	if (delta == -1) m++;
}
invalid |= !((p == 1 && m == 1) || (p == 0 && m == 0));

 * 오일러 서킷 구하는 DFS

circuit을 저장할 자료구조는 stack이든 vector든 상관없다. 나중에 거꾸로 읽어야 오일러 경로를 제대로 구할 수 있다. (양/무방향에서 오일러 회로는 거꾸로 하지 않아도 상관은 없다.)

코드 :

vector<int> c;
void dfs(int u) {
	for (int v = 0; v<N; v++)
		while (adj[u][v] > 0) {
			adj[u][v]--;
			dfs(v);
		}
	c.push_back(u);
}

// dfs를 호출한 곳에서 사용하면 된다.
if(c.size() != edge.size() + 1) return false; // 위에서 설명한 조건 1. Component가 여러개라면 방문한 간선수는 적을 것이다.
reverse(c.begin(), c.end());