Eulerian Path와 Circuit: 모든 간선을 정확히 한 번 사용하기

Eulerian Path는 그래프의 모든 간선을 정확히 한 번씩 사용하는 경로입니다.

Eulerian Circuit은 같은 조건을 만족하면서 마지막에 시작 정점으로 돌아옵니다.

Hamiltonian과의 차이

Eulerian은 간선을 중심으로 합니다.

모든 Edge를 정확히 한 번

Hamiltonian은 정점을 중심으로 합니다.

모든 Vertex를 정확히 한 번

Eulerian Path에서는 같은 정점을 여러 번 방문할 수 있습니다.

무방향 그래프 조건

Eulerian Circuit이 존재하려면:

• 간선을 가진 모든 정점이 하나의 연결 성분에 있어야 하고,
• 모든 정점의 degree가 짝수여야 합니다.

Eulerian Path는 정확히 두 개의 홀수 degree 정점을 허용합니다.

홀수 정점 0개 → Circuit
홀수 정점 2개 → Path
2개 초과 → Eulerian Trail 없음

Hierholzer 알고리즘

사용하지 않은 간선을 계속 따라가고, 더 이상 갈 간선이 없을 때 Stack에서 되돌아오며 결과를 구성합니다.

function eulerTrailDirected(graph, start) {
  const g = Object.fromEntries(
    Object.entries(graph).map(
      ([node, edges]) => [node, [...edges]]
    )
  );

  const stack = [start];
  const path = [];

  while (stack.length) {
    const current = stack[stack.length - 1];

    if ((g[current]?.length ?? 0) > 0) {
      stack.push(g[current].pop());
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

방향 그래프

Eulerian Circuit에서는 활성 정점마다:

inDegree = outDegree

가 필요합니다.

Eulerian Path에서는 시작 정점과 끝 정점에 각각 하나의 degree 불균형이 생길 수 있습니다.

복잡도

적절한 자료구조에서는:

O(V + E)

시간에 동작합니다.

실제 활용

• 도로 청소
• 네트워크 링크 점검
• Route Inspection
• 한 붓 그리기 퍼즐
• de Bruijn Graph 기반 DNA Assembly

정리

모든 간선을 덮는 것이 목표라면 Eulerian을 생각하고, 모든 정점을 한 번씩 방문하는 것이 목표라면 Hamiltonian을 생각하면 됩니다.