[자료구조/알고리즘] Eulerian circuit(한붓그리기)

Contents

Eulerian cirtuit(오일러 서킷)

Eulerian trail(오일러 트레일)

Eulerian Circuit(오일러 서킷)

오일러 서킷이라는 것은 우리들에게 한붓그리기 문제로 더 알려져 있습니다.

오일러 서킷

그래프가 주어졌을 때 그래프의 한 시작점으로부터 모든 간선을 한번씩만 지나 다시 시작점으로 돌아오는 경로를 말합니다.

이러한 경로가 있으려면 어떠한 조건을 만족해야 할까요?

가장 많이 사용되고 있는 방법으로는 단순하게 정점의 degree를 사용하는 것입니다.

degree라는 것은 위상정렬 할 때 잠시 살펴보았죠?

그 때는 indegree를 이용하였고, 여기서 degree라는 것은 정점에 연결되어 있는 간선의 수를 말합니다.

그런데 도대체 degree가 갑자기 왜나올까요?

1) 무향그래프인 경우

한붓으로 모든 간선을 그리고 돌아오는 경로를 한번 생각해 봅시다.

(여기서 모든 간선은 단 하나의 그래프로 모두 연결되어 있다고 합시다.)

붓은 시작점에서 부터 나가서, 모든 간선을 그리고 다시 시작점으로 돌아오겠죠.

그렇다면 여기서 시작점의 degree는 짝수일까요 홀수일까요?

degree는 짝수여야 합니다! 왜냐하면 degree가 홀수이면 나갔다가 마지막에 돌아올 수 없기 때문이죠.

자 이제 시작점이 아닌 다른점을 생각해 봅시다.

다른점의 degree는 짝수일까요 홀수일까요?

당연히 다른점의 degree또한 짝수여야 합니다.

왜 그런 것인지는 시작점이 짝수일 수 밖에 없었던 이유를 생각해 보시길 바랍니다!

그러면 지금까지 보아온 것들로 결론을 낼 수 있습니다.

우선 degree가 홀수 인 점이 있다면, 오일러 서킷은 존재하지 않습니다.

따라서 모든 정점의 degree는 짝수여야 합니다.

그리고 오일러 서킷의 존재성 보장을 위해 모든 간선이 한 그래프로 연결이 되어있어야 합니다.

무향 그래프에서 오일러 서킷이 존재하기 위한 조건

1) 모든 간선이 단 하나의 그래프에 연결되어 있을 때 (단일 컴포넌트)

2) 모든 정점의 degree가 짝수일 때

이제 무향그래프에서 이런 오일러 서킷을 찾는 방법에 대해서 생각해 봅시다.

우선 오일러 서킷이 존재하는 그래프가 있다고 가정합시다.

그렇다면 다음과 같은 순서로 오일러 서킷을 찾을 수 있습니다.

오일러 서킷을 찾는 방법

1. 임의의 그래프 내의 시작점 u를 정합니다.

2. 시작점 u에 대해 방문하지 않은 간선(u, v)이 있다면 그 간선을 따라 이동합니다.

3. 이동하여 도착한 정점 v에 대해서 또 다시 2번과 같이 방문하지 않은 간선이 있다면 따라서 이동합니다.

4. 3번을 반복하다가 더 이상 이동 할 간선이 없다면 이때까지 이동하였던 경로를 반환합니다.

5. 아직 방문하지 않은 간선에 대해 3번을 반복 수행하고 얻어지는 경로를 모두 합칩니다.

그런데 위와 같은 방식은 5번과 같이 여러개의 경로를 어떻게 합쳐야 하는가에 대한 이슈가 남게 됩니다.

나머지 번호는 dfs와 같이 재귀적으로 호출함으로서 해결이 가능합니다.

5번의 문제를 어떻게 해결 할 수 있을까요?

실제로 우리가 어떻게 경로를 찾아내는지 한번 붓을 들고 그려봅시다.

1번 노드를 시작점으로 하고, 연결된 간선 중 정점의 번호가 작은 것 부터 선택한다고 생각해 봅시다.

위에서 제시한 방법대로라면 아래와 같이 첫번 째 경로가 찾아집니다.

이제 정점 5번과 연결된 방문하지 않은 간선을 보면 다음과 같이 되겠죠.

우리가 사실 원하는 경로는 1-2-5-6-7-5-4-3-1 입니다.

여기서 DFS를 재귀적으로 함수를 구현했을 때 DFS함수의 호출이 종료되는 순서대로 정점을 한번 살펴봅시다.

정점1

정점3

정점4

정점5

정점7

정점6

정점5

정점2

정점1

순으로 함수가 종료가 될 것입니다.

지금 이 과정을 눈으로 잘 따라오셨다면 느낌이 살짝 오게 됩니다.

종료하는 시점에서 경로를 만들어 가면 자동적으로 모든 과정이 해결이 됩니다!

바로 DFS한번에 말이죠!

자 그럼 구체적으로 방법을 들여다 봅시다.

위의 그래프를 가지고 코드를 작성해 보았습니다.

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector< vector<int> > adj;
vector<int> euler;
 
/* DFS와 같은 방식으로 경로를 찾아갑니다. */
void findEulerianCircuit(int here) {
    for (int there = 1; there < adj.size(); there++) {
        while (adj[here][there] > 0) {
            adj[here][there]--;
            adj[there][here]--;
            findEulerianCircuit(there);
        }
    }
    euler.push_back(here);
}
 
int main() {
    adj = vector< vector<int> >(8, vector<int>(8, 0));
    euler.clear();
    adj[1][2] = adj[2][1] = 1;
    adj[2][5] = adj[5][2] = 1;
    adj[4][5] = adj[5][4] = 1;
    adj[3][4] = adj[4][3] = 1;
    adj[3][1] = adj[1][3] = 1;
    adj[5][7] = adj[7][5] = 1;
    adj[6][7] = adj[7][6] = 1;
    adj[5][6] = adj[6][5] = 1;
    findEulerianCircuit(1);
    reverse(euler.begin(), euler.end());
    for (int v : euler) {
        cout << v << " ";
    }
    cout << '\n';
}

13번째 line이 while인 경우는 두 정점간에 연결된 간선이 여러개 일수도 있기 때문입니다.

14-15 line에서는 연결된 간선이 방향이 없으므로 두쪽 모두 지워주어야 합니다.

문제 상황에서 두 정점간의 간선이 무조건 하나라면 while문이 없어도 됩니다!

findEulerianCircuit() 함수의 시간복잡도를 살펴봅시다.

간선마다 함수가 실행이 되고, 정점으로부터 간선을 찾는데 |V|만큼의 시간이 걸리므로

가 됩니다.

2) 유향그래프인 경우

이제 간선에 방향성분이 있는 경우를 생각해 봅시다.

아까 무향그래프에서 각 정점들의 degree가 짝수여야 하는 이유에 대해서 생각해 보면,

유향 그래프에서 오일러 서킷이 존재 할 조건 또한 쉽게 나오게 됩니다.

유향 그래프에서 오일러 서킷이 존재하기 위한 조건

1) 모든 간선이 단 하나의 그래프에 연결되어 있을 때 (단일 컴포넌트)

2) 모든 정점의 in-degree와 out-degree가 같을 때

유향 그래프에서 오일러 서킷을 찾는 방법은 무향그래프와 동일합니다!

간선을 지울때 양방향이 아니라 단방향을 지우는 것만 차이가 납니다.

간단한 문제 하나 풀고 다음 내용도 살펴봅시다

'Algorithm > Algorithm' 카테고리의 다른 글

[자료구조/알고리즘] 비트연산을 통한 순열 (0)	2021.01.11
[자료구조/알고리즘] 재귀 함수를 이용한 부분 집합 생성 알고리즘 (0)	2021.01.06
[자료구조/알고리즘] 해시(Hash) 란? (0)	2021.01.06

'Algorithm > Algorithm' 카테고리의 다른 글

티스토리툴바