오일러 트레일(Euler trail), 오일러 회로(Euler circuit)

기본 개념 정리

오일러 트레일

그래프의 모든 간선을 단 한번씩만 통과하는 길 혹은 방법 이 있으면, 오일러 트레일 이라고 한다.

그래프에서 간선은 방향이 있는 경우와 방향이 없는 경우로 나누어 생각 할 수 있다. 따라서 오일러 트레일 역시, 방향이 있는 경우와 방향이 없는 경우로 나누어 생각이 가능하다.

방향이 없는 경우, 오일러 트레일 필수 조건

1. 그래프의 모든 노드는 연결되어 있어야 한다. (연결 그래프)

2. 그래프의 노드중 홀수 차수를 가지는 노드가 0개 또는 2개 여야 한다.

• 그래프의 모든 노드 연결은, 오일러 문제의 기본 전제 조건이다.
• 그래프의 노드중 홀수 차수가 2개 이상인 경우, 실제 그리기를 해보면, 되돌아 갈 수 없거나, 마지막에 남은 두개의 노드중 한곳만 방문 가능한 형태가 나타난다.

방향이 있는 경우, 오일러 트레일 필수 조건

1. 그래프의 모든 노드는 연결되어 있어야 한다. (연결 그래프)

2. 그래프의 노드중 홀수 차수를 가지는 노드가 0개 또는 2개 여야 한다.

-- 홀수 차수 노드가 2개인 경우, 각각이 시작점, 도착점이 된다. --

3. 출발점는 나가는 간선이 들어오는 간선보다 하나 많아야 한다.

4. 도착점은 들어오는 간선이 나가는 간선보다 하나 많아야 한다.

5. 짝수 차수 노드는, 나가는 간선과 들어오는 간선의 수가 동일해야 한다.
   (Math.abs(InDegree - OutDegree) == 0)

6. 홀수 차수 노드는, 나가는 간선과 들어오는 간선의 차이가 1개여야 한다.
   (Math.abs(InDegree - OutDegree) == 1)

• 방향이 있는 경우가 실제 그리기를 해 보았을때 더 쉽게 이해 가능하다.
• 기본적으로 모든 간선을 방문해야 하는데, 출발점에서 나가는 간선이 들어오는 간선보다 많아야 모든 간선 방문이 가능하다. 머리속으로 상상해보면, 복잡한 여러 노드를 방문해서 다시 출발점에 왔을때, 들어오는 간선만 하나 남은 경우, 어딘가로 다시 나가는 간선이 있어야 해당 들어오는 간선을 사용 가능한 그림이 된다.
• 도착점은 출발점과 반대로 생각해보면 쉽게 이해 가능하다.

홀수 차수 노드가 2개인 경우, 특수 조건

홀수 차수 노드가 2개인 경우, 해당 두 노드를 출발점과 도착점으로 하여야 오일러 트레일이 성립된다.

오일러 서킷, 오일러 회로

오일러 트레일 개념에 더하여, 출발점과 마지막 도착점이 동일한 경우를, 오일러 서킷, 오일러 회로 라고 한다.

모든 간선을 방문 하되 항상 다시 출발점으로 돌아와야 하는 조건이 추가되어 있다. 따라서 오일러 트레일보다 가능한 조건이 더 타이트하게 되어 있다.

방향이 없는 경우, 오일러 서킷(회로) 필수 조건

1. 그래프의 모든 노드는 연결되어 있어야 한다. (연결 그래프)

2. 그래프의 모든 노드의 차수는 짝수여야 한다.

• 다시 시작점으로 돌아와야 하기 때문에 홀수 차수가 있으면 안된다. (다른 어딘가로 가게됨)
  • 차수가 짝수여야 하나는 나가는 간선, 하나는 들어오는 간선으로 처리하고, 원래 시작점으로 돌아 올 수 있다.

방향이 있는 경우, 오일러 서킷(회로) 필수 조건

1. 그래프의 모든 노드는 연결되어 있어야 한다. (연결 그래프)

2. 그래프의 모든 노드의 차수는 짝수여야 한다.

3. 그래프의 모든 노드의 나가는 간선 수와 들어오는 간선 수가 동일하게 있어야 한다.

• 방향이 없는 경우를 대입하면 쉽게 이해 할 수 있다. 방향이 없는 오일러 서킷(회로)에서 모든 노드의 차수가 짝수여야 하는 이유는 하나의 간선은 나가는 간선, 하나의 간선은 들어오는 간선으로 처리하기 때문이다. 이를 방향이 있는 그래프로 도입하면, 명확하게 나가는 간선수 만큼 들어오는 간선수가 존재하여야 원래 시작점으로 돌아 올 수 있다.

이론 핵심 요약

오일러 트레일, 오일러 서킷 모두 한붓그리기로 생각하면 된다.

• 모든 간선을 방문하는 알고리즘
  • 오일러 트레일: 그래프상 존재하는 모든 간선을 단 한번씩 방문 하는 것.
    • 무방향 그래프: 홀수차수 0 또는 2개, 홀수차수가 2개면 해당 두 노드가 출발, 도착
    • 방향 그래프: 무방향 그래프 조건 + 출발점은 나가는 차수가 하나 더 많아야 함, 도착점은 들어오는 차수가 하나 더 많아야 함.
  • 오일러 서킷: 오일러 트레일 + 원래 시작점으로 돌아오기.
    • 그래프상 존재하는 모든 간선을 단 한번씩 방문하되 처음 출발한 노드로 다시 돌아오는 것.
  • 방향 그래프, 무방향 그래프 모두 적용 가능하다.
  • 순환이 있어도 무방하다. 오일러 서킷 자체가 순환을 의미한다.
  • 그래프 관련 문제에서, 모든 간선을 방문해야하는 문제에 적용 가능하다.
• 복잡도
  • O(V + E), DFS 형태로 구현하게 된다.

구현 핵심 요약

Java로 설명한다.

• 위상정렬과 비슷한 형태의 구현이 가능하다. 단 위상 졍렬이나 DFS에서 방문 테이블(Visited 확인 테이블)을 사용하는 대신, 어떤 노드의 간선 수를 이용해서 처리하는 형태를 가진다.
• 간선 수를 줄여가면서 방문해야 하기 때문에 인접 행렬을 이용한 구현이 더 편리한 편이다.
• 인접 리스트로 구현시, 간선을 객체화 하여 구현하는 형태를 취하면 편리하다.
• 방향이 있는 경우, 들어오는 간선, 나가는 간선을 따로 관리해야 한다.

DFS 형태

필요한 요소

• 그래프를 표현한 자료구조 (ArrayList | Array) - e.g) int [][] graph
• 방문(path)저장 자료구조 (LinkedList) - e.g) LinkedList<Integer>path
• 출발 Node을 check하거나, 오일러 트레일이 가능한지 체크하귀 위한 용도의 차수 저장 자료구조 - e.g) int [] degree

코드

static int graph[][] = new int[YOUR_GRAPH_SIZE][YOUR_GRAPH_SIZE];
static LinkedList<Integer> path = new LinkedList<Integer>();

static void dfs(int node) {
    for (int i = 0; i < graph.length; i++) {
        while (graph[node][i] != 0) {
            graph[node][i]--;
            graph[i][node]--;
            dfs(i);
        }
    }

    path.addFirst(node);
}

주의 사항

• path 에 저장하는 node (순서)는 reverse 하여야 방문순서가 순서대로 나온다.
  • LinkedList을 사용하고 addFirst을 사용하면, reverse할 필요없이 방문순서가 나온다.
• 필요한 경우, 오일러 트레일(또는 오일러 서킷)이 가능한지 체크 하는 체크 함수가 필요할수 있음
• 필요한 경우, 오일러 트레일(또는 오일러 서킷)이 가능한 시작, 도착 점을 알아내야 하는 경우가 필요할수 있음
• 오일러 트레일(또는 오일러 서킷)의 가능 여부 혹은, 출발, 도착점을 알아야 하는경우 이론에 맞게 별도의 함수를 만들어서 사용하면 된다.

• // 오일러 트레일 가능 여부 확인
  static boolean checkEuler() {
      int degree[] = new int[YOUR_GRAPH_SIZE];
      int hol = 0;
  
      for (int i = 0; i < graph.length; i++) {
          for (int j = 0; j < graph.length; j++) {
              degree[i] += graph[i][j];
          }
      }
  
      for (int d = 0; d < degree.length; d++) {
          if (degree[d] % 2 == 1) {
              hol++;
          }
      }
  
      // 홀수 차수가 2개 또는 0개인 경우만 오일러 트레일 가능
      return (hol == 2 || hol == 0);
  }
  
  // 시작가능점 찾기
  static ArrayList<Integer> startPossible() {
      int degree[] = new int[YOUR_GRAPH_SIZE];
      ArrayList<Integer> holIndex = new ArrayList<Integer>();
      ArrayList<Integer> possibleIndex = new ArrayList<Integer>();
  
      for (int i = 0; i < graph.length; i++) {
          for (int j = 0; j < graph.length; j++) {
              degree[i] += graph[i][j];
          }
      }
  
      for (int d = 0; d < degree.length; d++) {
          possibleIndex.add(d);
          if (degree[d] % 2 == 1) {
              holIndex.add(d);
          }
      }
  
      if (holIndex.size() == 2) {
          return holIndex;
      }
  
      if (holIndex.size() == 0) {
          return possibleIndex;
      }
  
      return null;
  }