유향 그래프의 오일러 회로 판별 방법 완벽 가이드

오일러 경로(Euler Path)는 그래프의 모든 간선을 정확히 한 번씩만 지나가면서 방문할 수 있는 경로를 의미합니다. 이때 정점(vertex)은 여러 번 반복해서 방문해도 무방합니다.

오일러 회로(Euler Circuit)는 오일러 경로의 특수한 형태입니다. 오일러 경로의 시작 정점과 끝 정점이 서로 연결되어 있어, 출발점으로 다시 돌아올 수 있는 경우를 오일러 회로라고 부릅니다.

오일러 회로 판별 조건

주어진 유향 그래프(directed graph)가 오일러 회로를 가지는지 확인하려면 다음 두 가지 조건을 모두 만족해야 합니다.

• 연결성: 그래프가 연결되어 있어야 합니다. 유향 그래프의 경우 모든 정점 쌍이 서로 도달 가능한 강한 연결(strongly connected) 상태여야 합니다.
• 차수 일치: 모든 정점에 대해 진입 차수(in-degree)와 진출 차수(out-degree)가 동일해야 합니다.

입력 및 출력 형식

입력:
그래프의 인접 행렬(adjacency matrix)
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
1 0 0 0 0
0 0 1 0 0

출력:
오일러 회로가 존재합니다.

알고리즘

1. traverse(u, visited) — 깊이 우선 탐색

입력: 시작 노드 u와 방문 여부를 표시할 visited 배열

출력: u와 연결된 모든 정점을 순회

Begin
    u를 방문 처리한다
    u와 인접한 모든 정점 v에 대해 반복:
        v를 아직 방문하지 않았다면
            traverse(v, visited) 재귀 호출
    종료
End

2. isConnected(graph) — 연결성 검사

입력: 검사 대상 그래프

출력: 그래프가 연결되어 있으면 true, 아니면 false

Begin
    visited 배열을 선언한다
    그래프의 모든 정점 u에 대해 반복:
        모든 노드를 미방문 상태로 초기화
        traverse(u, visited) 실행
        아직 방문하지 않은 노드가 남아 있다면
            false 반환
    종료
    true 반환
End

3. isEulerCircuit(Graph) — 오일러 회로 판별

입력: 주어진 그래프

출력: 오일러 회로가 존재하면 true, 아니면 false

Begin
    isConnected()가 false라면
        false 반환
    각 노드의 진입 간선 수와 진출 간선 수를 저장할 리스트 생성

    그래프의 모든 정점 i에 대해 반복:
        sum := 0
        i와 연결된 모든 정점 j에 대해 반복:
            정점 i의 진입 간선 수 증가
            sum 증가
        정점 i의 진출 간선 수 = sum
    종료

    진입 리스트와 진출 리스트가 같으면
        true 반환
    아니면 false 반환
End

C++ 구현 예제

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0},
    {0, 0, 1, 0, 0}
};

// 깊이 우선 탐색으로 연결된 정점을 모두 방문
void traverse(int u, bool visited[]) {
    visited[u] = true;   // u를 방문 처리

    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

// 그래프의 연결성 검사
bool isConnected() {
    bool *vis = new bool[NODE];
    // 모든 정점을 시작점으로 삼아 전체 노드 방문 가능 여부 확인

    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i<NODE; i++)
            vis[i] = false;   // 모든 노드를 미방문 상태로 초기화

        traverse(u, vis);

        for(int i = 0; i<NODE; i++) {
            if(!vis[i])   // 방문하지 못한 노드가 있다면 그래프는 비연결
                return false;
        }
    }
    return true;
}

// 오일러 회로 판별 함수
bool isEulerCircuit() {
    if(isConnected() == false) {   // 그래프가 연결되어 있지 않은 경우
        return false;
    }

    vector<int> inward(NODE, 0), outward(NODE, 0);

    for(int i = 0; i<NODE; i++) {
        int sum = 0;
        for(int j = 0; j<NODE; j++) {
            if(graph[i][j]) {
                inward[j]++;   // 도착 정점의 진입 간선 수 증가
                sum++;         // 시작 정점의 진출 간선 수 계산
            }
        }
        outward[i] = sum;
    }

    if(inward == outward)   // 모든 정점에서 진입/진출 차수가 같은 경우
        return true;
    return false;
}

int main() {
    if(isEulerCircuit())
        cout << "오일러 회로가 존재합니다.";
    else
        cout << "오일러 회로가 존재하지 않습니다.";
}

실행 결과

오일러 회로가 존재합니다.

정리

유향 그래프에서 오일러 회로의 존재 여부는 크게 두 단계로 판별할 수 있습니다. 첫째, 깊이 우선 탐색(DFS)을 활용해 그래프의 연결성을 확인합니다. 둘째, 모든 정점의 진입 차수와 진출 차수가 일치하는지 비교합니다. 이 두 조건을 모두 통과하면 해당 그래프는 오일러 회로를 가진다고 결론지을 수 있습니다. 시간 복잡도는 정점 수를 V, 간선 수를 E라고 할 때 연결성 검사에 O(V²)(인접 행렬 기준), 차수 비교에 O(V²)가 소요됩니다.