[DFS] 오일러 서킷

오일러 서킷

깊이 우선 탐색을 이용해 풀 수 있는 또 다른 문제로, 그래프르이 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제가 있다. 이와 같은 경로를 그래프 이론에서는 오일러 서킷(Eulerian circuit)이라고 부른다.

오일러 서킷이 어느 경우에 존재할 수 있는지를 판단하는 단서는 반대로 오일러 서킷이 존재할 수 없는 경우는 무엇인가를 생각해보는 것이다. 일단 한가지 경우
그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우 존재할 수 없다.
※ 그래프의 정점이 둘 이상의 컴포넌트로 쪼개져 있더라도, 간선들이 한 컴포넌트에 있기만 하면 오일러 서킷은 존재한다. 예를들어 정점 a, b, c를 갖는 방향 그래프에 두 개의 간선 (a, b)와 (b, a)가 있다면 그래프는 연결되어 있지 않지만 오일러 서킷은 존재한다.

임의의 그래프에서 최대한 많은 간선을 지나는 경로를 그리는 방법을 알려주는 알고리즘이 있다고 할 때, 오일러 서킷이 존재한다면 오일러 서킷을 찾아 주겠지만, 그런 경로가 존재하지 않는다면 이 경로는 모든 간선을 지나지 못하고 끝나게 될 것이다.
이 경로의 시작점을 u, 끝점을 v라고 하자.이때 v에 인접한 모든 간선은 이미 지난 뒤여야 함을 쉽게 알 수 있다. 아직 지나지 않은 간선이 있다면 이 간선을 따라가 경로를 더 길게 할 수 있기 때문이다. 또한 다음과 같은 경우로 나눠 말할 수 있다.

아래는 모든 간선을 지나지 못하고 끝나는 경우의 2가지 경우

1. u != v 인 경우, 항상 v는 홀수 개의 간선과 인접해 있을 것이다. v를 지나가기 위해서는 v로 들어가는데 하나, 나가는 데 하나의 간선이 필요하고, 때문에 v로 들어가서 더이상 나올 수 없다는 말은 인접한 간선의 수가 홀수라는 의미이다.

2. u == v 인경우, v에 인접한 간선의 수는 항상 짝수다. u에서 나가는 것으로 시작했으니, 들어온 뒤 다시 나갈 수 없다면 지금까지 사용한 간선의 수는 항상 짝수여야하기 때문이다.

이로부터 각 정점에 인접한 간선의 수가 오일러 서킷의 존재 가능성과 밀접한 연관이 있음을 깨달을 수 있다. 
한 정점에 인접한 간선의 수를 해당 정점의 차수(degree)라고 부르자. 차수가 짝수인 정점을 짝수점, 홀수인 점을 홀수점으로 부르도록 하자.

앞의 두 경우 중 오일러 서킷의 존재 가능성에 더욱 직접적인 영향을 미치는 것은 홀수점이다. 오잉ㄹ러 서킷은 모든 정점에 들어가는 횟수와 나오는 횟수가 같아야 하는데, 홀주점이라면 이와 같은 일이 불가능하기 때문. 따라서 그래프의 모든 정점들이 짝수점이어야만 오일러 서킷이 존재할 수 있다는 결론을 얻을 수 있다.

홀수점이 하나라도 있을 때 오일러 서킷이 존재하지 않는다면, 그 역도 성립할까? 다시 말해 모든 정점이 짝수점이라면 오일러 서킷은 항상 존재할까? 다행이 모든 정점이 짝수점이면서, 간선들이 하나의 컴포넌트에 포함된 그래프가 주어질 때는 항상 오일러 서킷을 찾아내는 알고리즘을 만들 수 있다. 따라서 이 알고리즘은 오일러 서킷의 존재성에 대한 구성적 증명이 된다.

findRandomCircuit(u)

어떤 그래프의 모든 정점이 짜수점이고, 모드 간선이 하나의 컴포넌트에 포함되어 있다고 할때, 현재 정점에 인접한 간선 중 아직 따라간 적 없는 임의의 간선을 따라가기를 반복하다가, 더이상 따라갈 간선이 없을 때 종료한다.
그래프의 모든 정점은 짝수점이므로, 시작점 외의 다른 정점에서 종료하는 것은 불가능하다. 따라서 항상 시작점에서 끝나게 되고, 찾아낸 경로는 항상 서킷이 된다. 운 좋게도 이 서킷이 이미 모든 간선을 지나쳤다면 오일러 서킷을 찾은 셈이니 곧장 종료할 수 있다. 만약 아니라면 서킷의 각 정점들을 하나하나 돌아보며, 아직 따라가지 않은 간선과 인접해 있는 정점을 찾는다. 이 정점을 v라고 부르자.

v또한 작수점이었을 텐데, 우리가 처음에 찾은 경로가 v를 지나가면서 짝수 개의 간선을 사용했기 때문에 짝수 개의 간선이 남을 수 밖에 없다. 따라서 v에서 다시 findRandomCircuit()을 수행하면 새로운 서킷을 얻게 되고 두 서킷을 합친다. 이와 같은 일을 서킷이 모든 간선을 다 포함할 때까지 반복하면 오일러 서킷을 찾을 수 있다.

깊이 우선 탐색을 이용한 구현

public static void getEulerCircuit(int here, List<Integer> circuit){
		for(int there = 0; there < adj[here].length; ++there){
			while(adj[here][there] > 0){
				adj[here][there]--; // 양쪽 간선을 모두 지운다
				adj[there][here]--;
				getEulerCircuit(there, circuit);
			}
		}
		circuit.add(here);
	}

findRandomCircuit()을 깊이 우선 탐색처럼 재귀 호출로 구현한다. findRandomCircuit(u)는 u와 인접한 간선들을 하나하나 검사하면서, 아직 방문하지 않은 간선 (u, v)가 있다면 또다시 findRandomCircuit(v)를 호출한다. 더이상 따라갈 간선이 없으면 재귀호출을 종료하고 반환, 지금까지 따라온 간선들을 모으면 하나의 서킷이 된다. 이때 각 정점을 순회하면서 아직 지나지 않은 간선이 남아있는지 확인해야 한다.

재귀 호출의 반환 과정에서 해당 정점에 아직 간선이 남아 있는지를 확인하고, 남아 있다면 새 서킷을 만들어 가운데 끼워넣을 수 있다. 결과적으로 얻은 서킷을 뒤집어야 하는 문제는 있지만 훨씬 간단한 구현이 가능하다.

각 간선을 따라갈 때마다 getEulerCircuit() 함수를 호출하고, 그 내부에서는 O(|V|)의 반복문을 수행하기 때문에 이 알고리즘의 전체 시간 복잡도는 O(|V||E|)가 된다. 인접 리스트 표현을 쓰면 이것을 O(|E|)에 할 수 있지만, 인접 리스트 표현을 쓰면 반대쪽에서 오는 간선을 지우는 구현이 조금 까다로워 진다.

오일러 트레일

오일러 서킷처럼 그래프의 모든 간선을 정확히 한 번씩 지나지만, 시작점과 끝점이 다른 경로를 오일러 트레일(Eulerian trail)이라고 부릅니다.

점 a에서 시작해서 b에서 끝나는 오일러 트레일을 찾고 싶다고 할때, a와 b사이에 간선 (b, a)를 추가한 뒤 오일러 서킷을 찾는다. 그리고 (b, a) 간선을 지워서 서킷을 끊으면 우리가 원하는 오일러 트레일을 얻을 수 있다. 따라서 오일러 트레일의 존재 조건은 오일러 서킷과 별로 다를 것이 없다. 시작점과 끝점을 잇는 간선을 하나 추가한 뒤 모든 점이 짝수점이 되려면, 시작점과 끝점을 제외한 모든 점은 짝수점이고 시작점과 끝점은 홀수점이어야 한다.