오일러 경로, 회로 (Eulerian Trail)

 

오일러 경로 (Eulerian Trail)

: 그래프에 존재하는 모든 엣지를 1번씩만 방문하는 연속된 경로

   if 시작점 == 도착점 : 오일러 회로 (Circuit)      

 

 별 모양 그래프

 

 : 대표적인 오일러 회로

   시작점이 어디든 모두 출발점으로 되돌아 온다.

 

   모든 정점의 차수 : 2 (짝수)

   => 들어오는 간선이 있으면, 나가는 간선도 있어야 하므로 (시작점, 끝점 제외)

   => 항상 차수가 2의 배수 꼴로 붙는다.

                   

 

 

무향그래프인 경우

차수(Degree)가 홀수인 정점이 2개 -> 오일러 경로

                                        0개 -> 오일러 회로

 

 

오일러 회로가 존재한다면, 어떤 정점을 시작점으로 선택하든 오일러 경로를 만들 수 있다.

 

 

 

 

 

• 오일러 회로 구하기

현재 가장 널리 알려져있고, 가장 효율적인 알고리즘 : 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)를 사용하여 또 경로를 구해 삽입해야 한다.

=> DFS로 구현 가능

    : 정점을 방문하면서 해당 간선을 사용한 것으로 표시하거나 지우고 간선 양쪽의 차수를 1씩 줄여나간다.

     해당 정점의 방문 함수가 끝나는 순간 정점 번호 출력하면 이를 이어 붙인 것들이 정답이 된다.

 

 

 

 

 

• DFS로 오일러 회로 구현하기

 

{A, B, C} 순으로 방문했다고 가정하면,

다음 방문지는 D or E or F

 

D를 먼저 선택한 경우 : D -> A

A의 인접 정점이 없기 때문에 방문 끝

-> C로 돌아오면서 “A D” 출력

 

다음으로 정점 E 방문 : E -> {C, E, F, C}

C도 더 이상 인접 정점이 없으므로

“C E F C” 출력

 

마지막으로 C에서도 시작점인 A로 돌아가

“B A”를 출력하면

                                         

ADCEFCBA

 

 

 

 

출처 : 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)