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

오일러 경로와 오일러 회로

오일러 경로는 그래프에서의 모든 간선을 단 한번씩만 통과하는 경로이다.

오일러 경로의 출발점과 종료점의 구분이 없다면, 오일러 회로이다.

 

오일러 경로는 다음의 특징을 가진다:

• 무방향 그래프인 경우, 두 노드를 제외한 모든 노드가 짝수 개의 차수를 가진다. 두 노드는 홀수 개의 차수를 가진다.
  어디서든 순회를 시작해도 오일러 경로이다.
• 방향 그래프인 경우, 두 노드를 제외한 모든 노드가 같은 진출차수 및 진입차수를 가진다. 두 노드는 진출차수가 하나 더 많은 노드 하나와, 진입차수가 하나 더 많은 노드로 루성된다.
  진출차수가 하나 더 많은 노드가 출발점이고, 진입차수가 하나 더 많은 노드가 도착점이다.

 

오일러 회로는 다음의 특징을 가진다:

• 무방향 그래프인 경우, 모든 정점의 차수가 짝수이다.
• 방향 그래프인 경우, 모든 정점의 진출차수와 진입차수의 개수가 같다.

공통적으로, 반드시 연결그래프여야 한다.

 

그래프에서 오일러 경로 및 회로가 있는지 확인하기

주어진 그래프에서 오일러 경로를 찾는 알고리즘은 다음과 같다:

1. 간선들의 정보를 이용해서 인접 행렬 및, 진출차수, 진입차수, 또는 방향그래프인 경우 차수들을 정리한다.
2. 각 노드의 차수를 확인하면서, 오일러 경로인지와 회로인지 구분한다. 오일러 경로인 경우, 출발점과 종료점을 찾아둔다.)
3. 기본적인 조건이 맞다면, 이제 한붓그리기가 실제로 가능한지 확인한다.
   출발점부터 dfs를 하면서 간선들에 대해 마킹처리를 한다.
   오일러 회로인 경우, 그래프의 노드 아무 곳에서나 하면 된다.

인접 행렬 adj는 'adj[u][v] = 정수' 의 꼴이어야 한다.

즉, 노드 u에서 노드 v로의 경로의 개수를 저장해야 한다.

출발점에서 dfs를 하면서, 각 간선들에 대해 방문처리 해줘야 한다.

 

그렇게 거치치 않은 간선이 없다면, 오일러 경로 또는 회로가 맞는 것이다.