[그래프] Graph 3: Eulerian circuit 오일러 서킷, 오일러 트레일

1. 오일러 서킷 (Eulerian circuit) - 한붓 그리기

 

 

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

 

 

이와 같은 경로를 그래프 이론에서 오일러 서킷이라고 부른다.

 

 

오일러 서킷이 어느 경우에 존재할 수 있는지를 판단하는 단서는 반대로 오일러 서킷이 존재할 수 없는 경우를 생각하는것이다.

 

가장 생각하기 쉬운 경우는 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우이다.

(간선을 가지지 않은 컴포넌트는 예외)

 

 

 

 

정점의 차수(degree) 

 

시작점이 u이고 끝점이 v인 특정 경로 u->v 가 모든 간선을 지나지 못하고 끝났다고 해보자.

 

이는 v에서 연결된 간선은 전부 한번 씩 지나갔다는 것을 의미한다. (갈곳이 없다)

 

u != v:  

    항상 v는 홀수 개의 간선과 인접해 있을 것이다. v로 들어오는것, v로 나가는 것, v로 들어오는것...

    v로 들어왔다 = 홀수개.

 

u == v:

    간선이 짝수개 u에서 나가는 것, u로 들어오는것, u에서 나가는것, u로 들어오는것...

    u는 시작점이기 때문에 나가는 것으로 시작하므로

    항상 짝수여야한다.

 

 

이를 통해 정점에 인접한 간선의 수가 오일러 서킷의 존재 가능성과 밀접한 연관이 있다는 것을 알 수 있다.

 

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

 

오일러 서킷의 존재 가능성에 더욱 직접적인 영향을 미치는 것은 홀수점이다.

 

오일러 서킷은 모든 정점에 들어가는 횟수와 나오는 횟수가 같아야하는데. 홀수점은 이를 방해하기 때문이다.

 

따라서 모든 정점들이 짝수점이어야만 오일러 서킷이 존재한다는 것이다.

 

 

 

2. 오일러 서킷 탐색 알고리즘: 구성적 증명

 

 

 

모든 정점이 짝수점이면서 간선들이 하나의 컴포넌트에 포함된 그래프가 주어질 때는

항상 오일러 서킷을 찾아내는 알고리즘을 만들 수 있다.

 

 

임의의 정점 u에서 시작해 아직 따라가지 않은 간선중 하나를 따라가며 임의의 경로를 만드는 함수

findRandomCircuit(u)를 만들어보자.

 

 

이 함수는 현재 정점에 인접한 간선 중 아직 간적이 없는 임의의 간선을 지나가는 것을 반복하다가,

더이상 갈곳이 없을 때 종료된다.

 

 

그래프의 모든 정점은 짝수점이므로, 시작점외의 다른 정점에서 종료하는 것은 불가능하다.

(시작점에서 나갈때 시작점은 '홀수점'이 되기 때문에, 다른점은 들어가고 나가면 그대로 짝수점)

 

그러므로 항상 이 함수가 지나가는 경로는 서킷이된다.

 

만약 모든 간선을 지나가지 못했다면.

 

만들어진 서킷의 각 정점들을 하나씩 탐색해보며 아직 간선이 남아있는 정점을 시작점으로 삼아 

 

모든 간선을 지나갈때까지 이를 반복한다면 이는 오일러 서킷이 된다.

 

(모든 간선이 짝수이므로, 간선이 남아있는 정점의 남은 간선의 수 또한 짝수이다.)

 

 

 

3. DFS를 이용한 구현: 무향 그래프

 

 

 

링크드 리스트를 이용하여 이어 붙이기 연산을 하면 상수시간안에 두 서킷을 합쳐 오일러 서킷을 만들 수 있지만

 

다른 자료구조를 사용하면 길이에 비례하는 시간이 걸리기 때문에 구현하기 복잡하다.

 

DFS를 응용하면 간단하게 구현할 수 있다.

 

 

위에서 만들었던 findRandomCircuit(u) 함수를 깊이 우선 탐색처럼 재귀 호출하면

 

방문하지 않은 간선을 따라 내려가고, 이동할 수 없을때 종료되며 서킷이된다.

 

종료되고 난 다음 이전 정점들을 순회하면서 남은 간선이 있는 정점에서 새 서킷을 만들어 합치는 것이다.

 

 

vector<vector<int> > adj;
 
void getEulerCircuit(int here, vector<int>& circuit) {
    for(int there = 0; there < adj.size(); ++there) {
        while(adj[here][there] > 0) {
            adj[here][there]--;
            adj[there][here]--;
            getEulerCircuit(there, circuit);
        }
    } circuit.push_back(here);
}

 

각 간선을 따라갈 때 경로에 추가하는 것이 아니라 재귀 호출이 끝나고 반환할 때 서킷을 추가하는 것이므로

(재귀 호출이 끝나면 추가 = 경로의 끝점부터 역순으로 간선들이 추가)

 

두 서킷을 합치는 코드는 필요가 없다 그냥 지금까지 만든 부분의 맨 뒤에 붙이기만 하면 되는 것이다.

(어느 정점에 간선이 남아있는곳 까지 가게되면 서킷에는 지금까지 찾은 서킷의 뒷부분만이 저장되어있음)

 

또한 역순으로 추가되는 것이라서 결과적으로 나오는 서킷을 뒤집어야한다

(무향 그래프는 필요없다.)

 

 

인접 행렬로 표현되었기 때문에 모든 원소를 검사하고 

 

간선의 갯수만큼 함수를 호출하므로 총 O(|V||E|) 의 시간이 걸린다.

 

인접 리스트로 표현하게 되면 O(|E|)가 되지만 반대편 간선을 지우는것을 따로 구현해야한다.

 

 

 

4. 오일러 트레일 (Eulerian trail): 무향

 

오일러 서킷처럼 그래프의 모든 간선을 정확히 한번씩 지나지만,

 

시작점과 끝점이 다른 경로를 오일러 트레일(Eulerian trail)이라고 부른다.

 

이는 오일러 서킷을 찾는 문제와 동일하다

 

시작점과 끝점을 잇는 임시 간선을 넣으면 오일러 트레일은 오일러 서킷이 된다.

 

이를 통해 오일러 트레일의 시작점과 끝점은 홀수점이 되어야한다는 것을 알 수 있다.

 

또한 홀수 점에서 시작하게 되면, 항상 홀수점으로 끝나게 되므로 시작점만 찾으면 위 코드를 재활용 할 수 있다.

 

(현대 그래프 이론에서 경로는 한점을 한 번만 지나는 단순 경로를 말하므로 트레일이라고 부른다)

 

 

 

오일러 경로, 오일러 트레일 : 유향

 

 

5. 해밀토니안 경로

 

그래프의 모든 정점을 정확히 한 번씩 지나는 경로이다.

 

큰 그래프에 대해 이 경로를 빠르게 찾는 방법은 아직 고안되지 않았다.

 

유일한 방법은 조합 탐색이다.

 

즉 모든 정점의 배열을 하나하나 시도하는 것이다.

 

그러므로 최악의 경우 n!개의 후보를 만들어야한다.

 

 

 

- 알고리즘 문제해결전략 837p