오일러 경로(Euler Path)는 그래프의 모든 간선을 정확히 한 번씩만 지나가면서 탐색할 수 있는 경로를 의미합니다. 이때 정점(vertex)은 여러 번 방문해도 무방합니다. 오일러 회로(Euler Circuit)는 오일러 경로의 특수한 형태로, 경로의 시작 정점과 끝 정점이 동일한 경우를 말합니다. 즉, 출발점으로 다시 돌아오는 닫힌 경로가 오일러 회로입니다.
오일러 경로와 회로의 판별 조건
그래프에 오일러 경로나 오일러 회로가 존재하는지 확인하려면 다음 조건들을 만족해야 합니다.
- 연결 그래프여야 합니다. 그래프가 두 개 이상의 연결 요소로 나뉘어 있으면 오일러 경로나 회로는 존재할 수 없습니다.
- 차수(degree)가 홀수인 정점이 정확히 2개라면, 해당 그래프에는 오일러 경로가 존재합니다. 이때 홀수 차수를 가진 두 정점이 각각 경로의 시작점과 끝점이 됩니다.
- 홀수 차수를 가진 정점이 하나도 없다면, 해당 그래프에는 오일러 회로가 존재합니다.
입력과 출력
입력: 그래프의 인접 행렬 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 출력: 이 그래프에는 오일러 경로가 존재합니다.
알고리즘
오일러 경로/회로 판별은 크게 세 단계로 진행됩니다. 먼저 깊이 우선 탐색(DFS)으로 그래프의 연결성을 확인하고, 이후 각 정점의 차수를 계산하여 홀수 차수 정점의 개수를 세는 방식입니다.
1. traverse(u, visited) — 그래프 순회
입력: 시작 노드 u와 방문 여부를 표시하는 visited 배열
출력: 시작 노드에서 도달 가능한 모든 정점을 순회
Begin
mark u as visited
for all vertex v, if it is adjacent with u, do
if v is not visited, then
traverse(v, visited)
done
End2. isConnected(graph) — 연결성 검사
입력: 그래프
출력: 그래프가 연결되어 있으면 true, 아니면 false
Begin
define visited array
for all vertices u in the graph, do
make all nodes unvisited
traverse(u, visited)
if any unvisited node is still remaining, then
return false
done
return true
End3. isEulerian(Graph) — 오일러성 판별
입력: 주어진 그래프
출력: 오일러 그래프가 아니면 0, 오일러 경로만 존재하면 1, 오일러 회로가 존재하면 2
Begin
if isConnected() is false, then
return false
define list of degree for each node
oddDegree := 0
for all vertex i in the graph, do
for all vertex j which are connected with i, do
increase degree
done
if degree of vertex i is odd, then
increase oddDegree
done
if oddDegree > 2, then
return 0
if oddDegree = 0, then
return 2
else
return 1
EndC++ 구현 예제
#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
/* int graph[NODE][NODE] = {
{0, 1, 1, 1, 1},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{1, 0, 0, 1, 0}
};
*/ //주석 해제 시 오일러 회로 확인 가능
/* int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 1, 0}
};
*/ //주석 해제 시 비오일러 그래프 확인 가능
void traverse(int u, bool visited[]) {
visited[u] = true; //현재 정점을 방문 처리
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;
}
int isEulerian() {
if(isConnected() == false) //그래프가 연결되어 있지 않은 경우
return 0;
vector<int> degree(NODE, 0);
int oddDegree = 0;
for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++) {
if(graph[i][j])
degree[i]++; //간선이 발견되면 차수 증가
}
if(degree[i] % 2 != 0) //정점의 차수가 홀수인 경우
oddDegree++; //홀수 차수 정점 개수 카운트
}
if(oddDegree > 2) //홀수 차수 정점이 2개보다 많으면 오일러 그래프가 아님
return 0;
return (oddDegree)?1:2; //홀수 차수가 0개면 오일러 회로, 2개면 오일러 경로
}
int main() {
int check;
check = isEulerian();
switch(check) {
case 0: cout << "이 그래프는 오일러 그래프가 아닙니다.";
break;
case 1: cout << "이 그래프에는 오일러 경로가 존재합니다.";
break;
case 2: cout << "이 그래프에는 오일러 회로가 존재합니다.";
break;
}
}실행 결과
이 그래프에는 오일러 경로가 존재합니다.
정리
오일러 경로와 회로 문제는 1736년 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 해결하면서 처음 등장한 그래프 이론의 고전적인 주제입니다. 판별 알고리즘의 시간 복잡도는 인접 행렬 기준으로 O(V²)이며, 연결성 검사와 차수 계산 두 단계로 구성됩니다. 핵심은 홀수 차수 정점의 개수만 확인하면 되므로 매우 효율적이라는 점입니다.