Slow is better than NOTHING

Computer Science/4. Algorithm

오일러 경로와 회로(Eulerian trail & circuit)

Jeff_Kang 2019. 5. 18. 16:52
반응형

오일러 경로(Eulerian trail) 란 그래프에 존재하는 모든 Edge를 정확히 1번씩만 방문하는 연속된 경로입니다. 이때 시작점과 도착점이 같으면 오일러 회로(Circuit) 가 됩니다. 

오일러 회로

 가장 대표적으로 별 모양 그래프가 있는데 어느 점에서 시작하더라도 모두 출발점으로 되돌아 올 수 있습니다. 즉, 위 그래프는 오일러 회로가 존재합니다. 위 그래프를 다시 보면 모든 정점의 차수가 2(짝수)인데 시작점과 끝점을 제외하고서는 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 마련되어 있어야 하기 때문입니다. 그렇기에 항상 차수가 2의 배수꼴로 붙게 됩니다.

 

오일러 경로의 존재여부를 판단하는 방법은, 무향 그래프(non-directed graph)일 경우 Degree가 홀수 인 정점(Vertex)가 2개일때 오일러 경로가, 0개일 때 오일러 회로가 존재합니다.

오일러 경로는 존재하지만 오일러 회로는 존재하지 않는 그래프

오일러 경로는 시작점과 끝점을 차수가 홀수인 정점 2개로 하며, 오일러 회로만 존재한다면 그 어떤 정점을 시작점으로 뽑아도 만드는 것이 가능합니다.

 

◎ 오일러 회로 구하기

 

현재 가장 널리 알려졌고 효율적인 알고리즘은 Hierholzer's Algorithm 입니다.  (뭐라고 읽는것임..?)

방법은 다음과 같습니다.

 

 1) 아무 정점 v를 뽑고 v에서 출발해 v로 돌아오는 경로를 하나 뽑는다.

 2) 이때, 위 경로에 속해있는 정점 중 인접한 간선들 중에 경로에 쓰이지 않은, 즉 아직 방문되지 못한 간선이 있는 정점 u가 존재한다면, u로 시작해서 아직쓰이지 않는 간선들만 사용해 u로 돌아오는 경로를 하나 더 찾아 원래 경로에 끼워넣는다.

 

말이 복잡한데 그림과 함께 설명해보겠습니다.

예를 들어 아래와 같은 그래프가 있다고 했을때, 1번 공식에 따라 A라는 정점을 뽑고 A라는 정점에서 시작해 A라는 정점으로 들어오는 경로 {A,B,C,D,A} 를 뽑습니다.

 

 

그렇다면 2번 조건에따라 정점 C는 아직 사용하지 않는 간선이 존재하는 정점입니다.

 따라서 정점 C를 시작점으로 해서 돌아오는 경로 {C,E,F,C}를 찾아 원래의 경로에서 C가 있던 자리에 끼워넣으면 됩니다.

 

{A,B,C,D,A} -> {A,B,[C,E,F,C],D,A}

 

만약 그래프에서 사용되지 않은 인접 간선이 있다면 이를 Recursive하게 구현하여 또 경로를 구해 끼워 넣어야합니다. 

이걸 구현하는 방법은 Recursive Call에서 눈치 채신 분도 있으실거라 생각합니다. 네, DFS(Depth Search First)로 구현할 수 있습니다.

 

정점을 방문하면서 해당 간선을 사용한것으로 표시하거나 지우고 간선 양쪽의 차수를 1씩 줄어나가는데 해당 정점의 방문 함수가 끝나는 순간 정점 번호를 출력하면 이걸 이어붙인게 정답이 됩니다.

 

예를 들어

 위와 같은 그래프를 DFS할때,

 {A,B,C} 순으로 방문했다고 한다면 다음 방문지는 D,E또는 F가 될 수 있습니다. D를 먼저 선택했다고 했을 때, D->A로 가서 A의 인접 정점이 없기 때문에 방문이 끝나 C로 돌아오면서 "A D" 를 출력하게 됩니다. 그 다음 정점 E를 방문해서

{C,E,F,C} 로 가면 C도 더이상 인접 정점이 없으므로 "C E F C" 를 출력하고 C에서도 시작점인 A로 돌아가면서 "B A"를 출력해서 이어붙이면

 

$$A D C E F C B A$$ 

가 되어서 오일러 회로입니다.

만약 {A,B,C} 순으로 방문하고 D가 아니라 E를 방문했다고 하더라도, {C,E,F,C}를 방문한 후 C에서 유일하게 남은 D를 방문하기 때문에 결과는 동일합니다.

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220800097205&proxyReferer=https:%2F%2Fwww.google.com%2F

 

오일러 경로(Eulerian Path), 오일러 회로(Eulerian Circuit) (수정: 2019-08-20)

이번에 소개할 내용은 오일러 경로(Eulerian trail) 및 오일러 회로(Eulerian circuit)입니다.위상수학, ...

blog.naver.com

 

반응형

'Computer Science > 4. Algorithm' 카테고리의 다른 글

DP와 Greedy Algorithm  (0) 2019.05.18
DP(Dynamic Programming)  (0) 2019.05.18
P/NP 문제  (0) 2019.05.18