오일러 서킷

오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로

-> 한붓그리기

 

그래프의 시작점을 u, 끝점을 v라고 하자

 

1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접한다.

v를 지나기 위해서 v로 들어가는데 하나, 나가는데 하나가 필요하다. 만약 v가 끝점이라면 v로 들어가는 간선에 대응하는 나가는 간선이 없다는 뜻이므로 v에 인접한 간선의 수가 홀수 일 수밖에 없다.

 

2. u == v 인 경우 : v는 항상 짝수 개의 간선과 인접한다.

u에서 나가는 것으로 시작했기 때문에 u로 다시 들어왔다면 u(=v)에 인접하는 간선의 수는 짝수이다.

 

 

한 정점에 인접한 간선의 개수를 degree라고 하자.

오일러 서킷은 모든 정점에 들어가는 횟수와 나가는 횟수가 같아야하므로 모든 정점의 degree가 짝수여야 한다.

그렇다면 모든 정점의 degree가 짝수라면 어떤 그래프던지 오일러서킷은 항상 존재하는가?

- 모든 정점의 degree가 짝수이고, 간선들이 하나의 component에 포함되었다면 항상 오일러 서킷은 존재한다!

 

 

구현

// 그래프를 인접행렬로 표현 adj[i][j] = i와 j사이의 간선의 수
vector< vector<int> > adj;

// 양방향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷을 계산
// 결과로 얻어지는 circuit를 뒤집으면 오일러 서킷이 된다.
void getEulerCircuit(int now){
	for(int i = 0; i < adj[now].size(); i++){
    	while(adj[now][i]) > 0){
            adj[now][i]--;
            adj[i][now]--;
            getEulerCircuit(i);
        }
    }
    
    circuit.push_back(now);
}

각 간선을 따라갈 때마다 getEulerCircuit()을 호출하고, 내부에서는 O(V) (정점의 개수) 만큼의 반복문을 수행하기 때문에 전체 시간복잡도는 O(|V||E|)가 된다.

 

인접리스트 표현을 사용하면 O(|E|)만에 수행이 가능하지만 반대쪽에서 오는 간선을 지우는 adj[i][now]--; 부분의 구현이 까다로워진다는 단점이 있다.