[5][그래프 이론] - 오일러 서킷, 한붓그리기 (Eulerian Circuit)

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

오일러 서킷이란 한 정점에서 시작해서 모든 간선을 지나 시작 정점으로 돌아오는 것을 의미한다.

 

오일러서킷의 예 : 1번 정점에서 시작해 모든 간선을 순회한뒤 1번으로 돌아온다.

 

---

 

2. 오일러 서킷의 조건

정점들과 간선들이 주어졌을때, 해당 자료에서 오일러 서킷이 존재하는지 판단하려면 어떻게 해야할까?

 

오일러 서킷이 되기위한 2가지 조건은 다음과 같다.

 

1. 모든 간선들이 하나의 컴포넌트에 속해야한다.

2. 각 정점마다 간선의 수가 짝수개여야한다.

 

그 이유에 대해 하나씩 알아보자.

 

2-1. 모든 간선들이 하나의 컴포넌트에 속해야한다.

 

 

위와같은 경우 각 컴포넌트별로는 오일러서킷이 존재하지만, 전체 정점들로 보았을때는 컴포넌트간 순회 할 수 없기때문에 반드시 모든 간선들이 하나의 컴포넌트에 속해야한다.

 

 

---

2-2. 각 정점마다 간선의 수가 짝수개여야한다.

 

각 정점마다 간선의 수가 짝수여야한다는 의미는 위의 그림처럼 2번 정점에서 뻗어나간 간선이 4개인것 처럼 모든 정점에 대해 뻗어나간 간선들의 개수가 짝수개여야 한다는것이다.

 

그 이유는 간단하다. 만약 아래와같은 그래프가 있고 u 정점에서 출발해서 v정점을 경유하는 경우라고 생각하자.

 

 

중간의 간선들을 통과하다가 1번 정점에서 v로 들어간 후

 

 

v 정점에서 나와 2번 정점으로 간다.

 

 

이후 다시 3번 정점에서 v정점으로 들어가면, v정점에서는 다시 나올수가 없다. 따라서 시작 정점인 u 정점으로 돌아갈수 없고 오일러 서킷을 만족시키지 못함을 알수있다.

 

 

따라서 그래프내에 속한 어떠한 하나의 정점이라도 연결된 간선의 수가 홀수개면 한번 들어간 후 나올수 없으므로 오일러 서킷을 만족시키지 못한다.

 

따라서 모든정점에 있어서 연결된 간선의 수가 짝수여야한다.

 

---

3. 구현

오일러 서킷은 DFS로 간단하게 구현할 수 있다.

 

아직 방문하지 않은 간선들을 2차원 배열에 저장해놓고 DFS를 수행하면서 모든 간선을 방문했을때 오일러 서킷을 발견할 수 있다.

 

아래와같이 구현하게 되면 모든 오일러서킷을 구할 수 있다.

 

+ 오일러 서킷은 방향이 없는 그래프이므로 하나의 간선 (a,b)가 존재한다면 (b,a)도 존재한다.

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int n,k;
int v[101][101];
stack<int> s;
stack<int> answer;


void euerian_circuit(int start){
    if(k == 0){ // 오일러서킷 발견했을때
        answer = s;
        while(answer.size() > 0){
            cout << answer.top() << " ";
            answer.pop();
        }
        cout << start << endl;
    }
    else{
        for(int now = 0; now < n; now++){
            if(now != start && v[start][now] > 0){ 
                // 현재정점과 이동할 정점이 같지않으면서 해당 목적지 정점으로 남은 간선이 존재할때
                k--;
                v[start][now]--;
                v[now][start]--;
                s.push(now);
                euerian_circuit(now);
                k++;
                v[start][now]++;
                v[now][start]++;
                s.pop();
            }
        }
    }
}

int main(){
    int x,y,start;
    cin >> n; // 정점개수
    cin >> k; // 간선개수
    cin >> start; // 시작정점
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            v[i][j] = 0;
        }
    }

    for(int i=0; i<k; i++){
        cin >> x;
        cin >> y;
        v[x][y] = v[x][y] + 1; 
        v[y][x] = v[y][x] + 1; 
    }


    euerian_circuit(start);
}

/*
input 

5
7
1
0 1
0 2
1 2
1 3
2 3
1 4
2 4

output
1 4 2 3 1 2 0 1
1 3 2 4 1 2 0 1
1 4 2 1 3 2 0 1
1 2 4 1 3 2 0 1
1 3 2 1 4 2 0 1
1 2 3 1 4 2 0 1
1 4 2 3 1 0 2 1
1 3 2 4 1 0 2 1
1 4 2 0 1 3 2 1
1 0 2 4 1 3 2 1
1 3 2 0 1 4 2 1
1 0 2 3 1 4 2 1
1 4 2 1 0 2 3 1
1 2 4 1 0 2 3 1
1 4 2 0 1 2 3 1
1 0 2 4 1 2 3 1
1 2 0 1 4 2 3 1
1 0 2 1 4 2 3 1
1 3 2 1 0 2 4 1
1 2 3 1 0 2 4 1
1 3 2 0 1 2 4 1
1 0 2 3 1 2 4 1
1 2 0 1 3 2 4 1
1 0 2 1 3 2 4 1
*/