Eulerian Path

• 그래프의 모든 간선을 정확히 한 번씩 지나가는 경로
  • 쾨니히스베르크의 다리 문제
  • 시작점 != 끝점 일 수 있다
  • 시작점
    • 차수가 홀수
  • 중간 저점
    • 차수가 짝수
  • 끝점
    • 차수가 홀수
  • 일반화
    • 홀수 차수가 없거나, 오직 두 개만 존재해야 한다
      • 시작점으로 돌아오는 경우
        • 시작점이 짝수 차수여야 한다
    • 모든 정점이 짝수 차수라면 오일러 순환이 존재
  • $O(n^2)$
• 오일러 순환 (Eulerian Circuit or Cycle)
  • 시작점 == 끝점
• 오일러 그래프
  • 오일러 순환이 존재하는 그래프