오일러 서킷

Jewook·2022년 8월 4일

그래프 알고리즘

알고리즘

목록 보기

11/14

모든 정점에 연결된 간선이 짝수개이고 모든 간선이 한 Componenet에 있으면 오일러 서킷이 존재함을 보일 수 있다.

아이디어를 요약하자면,

남은 간선이 있으면 계속 그려나가는 식으로 trail을 그려보자. 어떻게 그려도 시작점 외의 다른 곳에서 끝나는 것이 불가능함을 보인다.
-> 정점과 연결된 간선이 모두 짝수개임을 이용하면 쉽게 보일 수 있다.
dfs를 이용하면 형태와 무관하게 어떻게든 모든 간선을 다 지나는 trail을 구하게 된다.
1과 2를 종합하면, 모든 간선을 다 지나는 trail을 dfs로 만들 수 있는데 시작점과 종착점은 같을 수 밖에 없으므로 dfs를 통해 만들어낸 trail은 오일러 서킷이 됨을 구성적으로 증명하게 된다.

무향 그래프

인접 행렬 O(VE)

int adj[N][N]; // i-j 간선의 수
deque<int> circuit;

void dfsEuler(int here) {
	for (int there =0; there < N; ++there) {
    	while (adj[here][there] > 0 ) {
        	adj[here][there]--;
            // 방향그래프인 경우 아래코드 사용하지 않음
            adj[there][here]--;
            dfsEuler(there);
        }
    }
	circuit.push_front(here);
}

인접행렬 최적화

int start[N], adj[N][N]; // i-j 간선의 수
deque<int> circuit;

void dfsEuler(int here) {
	for (int there =start[here]; there < N; ++there) {
    	start[here] = there;
    	while (adj[here][there] > 0 ) {
        	adj[here][there]--;
            // 방향그래프인 경우 아래코드 사용하지 않음
            adj[there][here]--;
            dfsEuler(there);
        }
    }
	circuit.push_front(here);
}

dfs를 이용했지만 근본적으로 다르다. 같은 정점을 중복 방문하지 않는 것이 아니라, "같은 간선"을 중복 방문하지 않는다. 따라서 한 정점에 대한 dfs가 여러번 호출될 수 있다. 그때마다 인접행렬에서 이미 처리한 간선들을 다 루프돌기에는 시간이 아깝다. start배열의 역할을 잘 이해하면 될 것 같다.

인접 리스트

인접 리스트에는 간선의 포인터나 인덱스만 저장해두고 실제 간선 정보는 따로 저장해두는 방법

struct Edge {
    int u, v, cnt;
};

// 간선배열 edge의 인덱스가 저장돼있음
vector<int> adj[N];
vector<Edge> edge;
deque<int> circuit;

void dfsEuler(int here) {

    while (!adj[here].empty()) {
        int idx = adj[here].back();
        auto& e = edge[idx];
        if (e.cnt > 0) {
            e.cnt--;
            dfsEuler((e.u == here) ? e.v : e.u);
        }
        else
            adj[here].pop_back();
    }
    circuit.push_front(here);
}

방향 그래프

조건은 비슷하다.
모든 정점이 outdegree == indegree 조건을 만족하면 오일러 서킷이 존재한다.

위 코드들을 아주 약간만 변형하면 된다.

오일러 경로

모든 간선을 다 지나되, 시작점과 도착점이 다른 경우이다.

무향그래프
두 정점만 차수가 홀수인 경우 오일러 경로가 존재한다. 각각이 시작점과 도착점이 된다. 둘 중 아무 정점을 시작점으로 오일러 서킷을 찾는 알고리즘을 적용하면 오일러 경로를 찾을 수 있다. 시작점과 도착점은 차수가 홀수인 정점 외에 불가능함을 쉽게 보일 수 있다.
방향그래프
전부 out, in 차수가 같고, 시작점은 out이 1 높고 도착점은 in이 1높은 경우 오일러 경로가 존재한다. 마찬가지로 오일러 서킷을 찾는 알고리즘을 적용하면 경로를 찾을 수 있다.