오일러 경로(Euler Path)란 그래프의 모든 간선을 정확히 한 번씩 지나갈 수 있는 경로를 말합니다. 이때 정점(vertex)은 여러 번 다시 방문해도 무방합니다. 또한 오일러 회로(Euler Circuit)를 포함하는 그래프 역시 오일러 경로를 가지므로 함께 고려 대상이 됩니다.
유향 그래프(directed graph)에 오일러 경로가 존재하는지 확인하려면 아래 세 가지 조건을 모두 검사해야 합니다.
- 진출 차수(out-degree)가 진입 차수(in-degree)보다 정확히 1 큰 정점이 단 하나만 존재해야 합니다. (진입 차수 + 1 = 진출 차수)
- 진입 차수가 진출 차수보다 정확히 1 큰 정점이 단 하나만 존재해야 합니다. (진입 차수 = 진출 차수 + 1)
- 나머지 모든 정점은 진입 차수와 진출 차수가 서로 같아야 합니다. (진입 차수 = 진출 차수)
위 조건 중 하나라도 충족되지 않으면 해당 그래프에는 오일러 경로가 존재하지 않습니다.
아래 예시 그래프에서 정점 b는 (진입 차수 1, 진출 차수 2), 정점 c는 (진입 차수 2, 진출 차수 1)을 가지며, 나머지 정점 a와 d는 (진입 차수 2, 진출 차수 2), 정점 e는 (진입 차수 1, 진출 차수 1)을 가집니다. 따라서 이 그래프는 오일러 경로를 가집니다.
입력
그래프의 인접 행렬(adjacency matrix)입니다.
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
출력
Euler Path Found. (오일러 경로가 발견되었습니다.)
알고리즘
traverse(u, visited)
입력: 시작 노드 u와, 방문 여부를 표시하기 위한 visited 배열
출력: 연결된 모든 정점을 순회합니다.
시작
u를 방문한 것으로 표시
u와 인접한 모든 정점 v에 대해 반복
v를 아직 방문하지 않았다면
traverse(v, visited) 호출
반복 종료
종료
isConnected(graph)
입력: 그래프
출력: 그래프가 연결되어 있으면 true
시작
visited 배열 정의
그래프의 모든 정점 u에 대해 반복
모든 노드를 미방문 상태로 초기화
traverse(u, visited) 호출
아직 방문하지 않은 노드가 남아 있다면
false 반환
반복 종료
true 반환
종료
hasEulerPath(Graph)
입력: 주어진 그래프
출력: 오일러 경로(또는 오일러 회로)가 존재하면 true
시작
an := 0
bn := 0
isConnected()가 false이면
false 반환
각 노드의 진입/진출 간선 개수를 저장할 리스트 정의
그래프의 모든 정점 i에 대해 반복
sum := 0
i와 연결된 모든 정점 j에 대해 반복
정점 i의 진입 간선 수 증가
sum 증가
반복 종료
정점 i의 진출 간선 수 := sum
반복 종료
진입 리스트와 진출 리스트가 완전히 같으면
true 반환 (오일러 회로이므로 오일러 경로도 존재)
정점 집합 V의 모든 정점 i에 대해 반복
inward[i] ≠ outward[i]이면
inward[i] + 1 = outward[i]이면
an := an + 1
아니고 inward[i] = outward[i] + 1이면
bn := bn + 1
an과 bn이 모두 1이면
true 반환
그렇지 않으면 false 반환
종료
예제 코드
#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 0, 1, 1, 0},
{1, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 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];
//모든 정점 u를 시작점으로 삼아 모든 노드를 방문할 수 있는지 확인
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 hasEulerPath() {
int an = 0, bn = 0;
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; //오일러 회로이며, 오일러 경로도 존재함
for(int i = 0; i<NODE; i++) {
if(inward[i] != outward[i]) {
if((inward[i] + 1 == outward[i])) {
an++;
} else if((inward[i] == outward[i] + 1)) {
bn++;
}
}
}
if(an == 1 && bn == 1) { //an과 bn이 각각 하나뿐이라면 오일러 경로가 존재함
return true;
}
return false;
}
int main() {
if(hasEulerPath())
cout << "Euler Path Found.";
else
cout << "There is no Euler Circuit.";
}
실행 결과
Euler Path Found.
위 프로그램은 먼저 그래프의 연결성을 DFS 순회로 확인한 뒤, 각 정점의 진입 차수와 진출 차수를 계산하여 오일러 경로의 존재 조건을 검사합니다. 모든 정점에서 진입 차수와 진출 차수가 같으면 오일러 회로가 존재하고, 조건을 만족하는 정점이 각각 정확히 하나씩만 있으면 오일러 경로가 존재한다고 판별합니다.