오일러 회로(Eulerian Circuit), 오일러 트레일(Eulerian Trail)

오일러 회로/트레일은 그래프에 존재하는 모든 간선(Edge)을 1번씩만 방문하는 회로/트레일입니다.

회로와 트레일의 차이점은 뭘까요?

 

회로 / 트레일

위 이미지가 회로와 트레일의 예시인데요, 회로는 배터리에서 시작해서 배터리로 끝나지만, 트레일은 A에서 B로 가기 때문에 출발점과 도착점이 다르죠? 이 점을 생각하시면 될 것 같습니다.

 

• 회로(Circuit, Cycle): 출발점 == 도착점
• 트레일(Trail): 출발점 != 도착점

현대 그래프 이론에서 경로(path)는 한 점을 한 번만 지나는 단순 경로를 가리킵니다. 오일러 트레일은 한 점을 여러번 지날 수도 있기에 경로 대신 트레일이라 부릅니다.

 

오일러 회로

위 그림은 별 모양 그래프인데요, 각 정점(Node)에서의 차수(degree, 간선의 갯수)가 전부 짝수인 2로, 어느 점에서 시작하더라도 모두 출발점으로 되돌아오는 오일러 회로를 만들 수 있습니다.

 

오일러 트레일

반면 위 그래프에서는 차수가 홀수인 정점이 2개 있는데, 이 때문에 오일러 트레일만 존재합니다.

 

오일러 회로/트레일은 한붓 그리기라고도 합니다

 

 

오일러 회로의 조건

어떤 그래프가 오일러 회로를 가질 필요충분조건은 모든 꼭지점이 짝수점(=차수가 짝수인 점)이어야 합니다.

이 때 시작점과 끝 점은 아무 점이나 가능합니다.

 

 

오일러 트레일의 조건

홀수점이 두개인 경우 오일러 트레일입니다. 이 때 시작과 끝 정점이 홀수 점이 됩니다.