오일러 회로

정의. 오일러 경로는 그래프의 모든 간선을 지나는 경로입니다.

정의. 오일러 회로는 회로를 이루는 오일러 경로입니다.

간단히 하기 위해 두 경우 모두 그래프가 무방향 그래프라고 가정하겠습니다.

또한 해밀턴 경로와 사이클이라는 개념도 있습니다. 이들은 간선이 아니라 모든 정점을 한 번씩 방문합니다. 해밀턴 사이클을 찾는 문제(외판원 문제, 영어로 travelling salesman problem)는 가장 잘 알려진 NP-완전 문제 중 하나인 반면, 오일러 사이클을 찾는 문제는 선형 시간에 해결되며, 그 방법을 지금부터 보이겠습니다.

#오일러 회로 찾기

정리. 오일러 회로는 그래프가 연결되어 있고 모든 정점의 차수가 짝수일 때, 그리고 그때에만 존재합니다.

증명. 필요성은 다음과 같이 보일 수 있습니다. 오일러 회로를 하나 잡고, 그 모든 간선을 순회 순서대로 방향을 정하면 됩니다. 그러면 각 정점에서 나가는 간선의 수와 들어오는 간선의 수가 같아지므로, 원래의 무방향 그래프에서 모든 정점의 차수는 짝수였다는 것을 알 수 있습니다.

충분성은 구성적으로 증명하겠습니다. 즉, 사이클을 찾는 알고리즘을 제시하겠습니다:

void euler(int v) {
    while (!g[v].empty()) {
        u = *g[v].begin(); // берем любое ребро
        remove_edge(v, u); // удаляем его
        euler(u);            // запускаемся от противоположного конца
    }
    cout << v <<  " ";     // выписываем текущую вершину
}

다음을 관찰할 수 있습니다:

• 정확히 $(m + 1)$개의 정점으로 이루어진 수열이 출력되며,
• 출력된 정점들 중 인접한 모든 쌍 사이에는 간선이 있으며,
• 각 간선은 정확히 한 번씩 기록됩니다.

따라서 연결성과 차수의 짝수 조건이 충족된다면, 출력된 정점 순서는 실제로 오일러 회로가 되며, 이는 방향 그래프의 경우에도 마찬가지입니다.

#간선을 삭제하는 방법

가장 간단한 방법은 모든 인접 리스트를 set과 같은 구조에 저장하고 그곳에서 직접 간선을 삭제하는 것입니다:

const int maxn = 1e5;
set<int> g[maxn];

void euler(int v) {
    while (!g[v].empty()) {
        u = *g[v].begin();
        g[v].erase(u);
        g[u].erase(v); // если граф ориентированный, обратное ребро удалять не надо
        euler(u);
    }
    cout << v <<  " ";
}

이 방법은 $O(m \log n)$ 시간에 동작하지만, 트리를 해시 테이블(unordered_set)로 바꾸기만 해도 시간을 선형으로 줄일 수 있습니다.

간선이 어떤 식으로든 변경되는 문제에서 자주 쓰이는 더 일반적인 방법을 사용할 수도 있습니다. 간선에 대한 메타 정보를 담은 별도의 배열을 만들고, 인접 리스트에는 정점 번호 대신 간선 번호를 저장합시다:

struct edge {
    int to;
    bool deleted;
};

vector<edge> edges;
stack<int> g[maxn];

void add_edge(int u, int v) {
    g[u].push(edges.size());
    edges.add({v, false});
    g[u].push(edges.size());
    edges.add({u, false});
}

무방향 그래프의 각 간선을 add_edge로 추가하면, 그 결과로 얻어지는 간선 번호 매기기에는 흥미로운 성질이 있습니다. 간선 e의 역방향 간선을 얻으려면 e^1을 계산하면 됩니다.

그러면 구조를 복잡하게 수정하는 대신, 탐색하는 동안 이 정보를 유지하면 됩니다.

void euler(int v) {
    while (!g[v].empty()) {
        e = g[v].top();
        g[v].pop();
        if (!edges[e].deleted) {
            edges[e].deleted = edges[e^1].deleted = true;
            euler(e.to);
        }
    }
    cout << v <<  " ";
}

모든 구현 방식에서 그래프에 루프와 다중 간선이 있는 경우에는 조금 더 주의해야 합니다.

#오일러 경로

이제 오일러 경로에 대해 이야기해 봅시다. 모든 정점의 차수가 짝수인 것은 아니더라도, 그래도 무언가 할 수 있지 않겠습니까?

각 간선은 정확히 두 정점의 차수의 홀짝성을 바꾸고, 빈 그래프에서는 처음에 모든 차수가 0이므로, 차수가 홀수인 정점의 개수는 짝수라는 점에 주목합시다.

홀수 차수 정점이 정확히 두 개라면 다음과 같이 할 수 있습니다. 두 정점을 간선으로 연결하고, 오일러 회로를 구성한 다음(이제 모든 정점의 차수가 짝수이기 때문입니다), 이 간선을 회로에서 제거합니다. 이 회로를 올바르게 회전시키면 오일러 경로를 얻게 됩니다.

또는, 단순히 홀수 차수 정점 중 하나에서 탐색을 시작해도 같은 결과를 얻을 수 있습니다.

홀수 정점이 두 개보다 많으면 더 이상 오일러 경로를 만들 수 없습니다. 오일러 경로는 양 끝점이 될 수 있는 두 정점을 제외한 모든 정점에 짝수 번 들어가거나 나오기 때문입니다.

따름정리. 오일러 경로는 그래프가 연결되어 있고 차수가 홀수인 정점의 개수가 2 이하일 때, 그리고 그때에만 존재합니다.

연습 문제. 연결된 무향 그래프가 주어집니다. 이 그래프의 간선을 서로 겹치지 않는 최소 개수의 경로로 덮어야 합니다. 시간 복잡도는 $O(n + m)$입니다.

연습 문제. 방향 그래프의 경우에 대해 유사한 명제를 세우고 증명하십시오.