02. 모든 길을 한 번씩: 오일러 회로(Eulerian Circuit)

1. 학습 목표 (Learning Objectives)

  • 초등학교 시절 무수히 그려보던 일명 ‘한붓그리기’ 가 수학적으로 정확히 어떤 조건에서만 100% 발동되는지 오일러의 정리 법칙을 해부합니다.
  • 지나가는 길(Edge)을 중복 없이 모조리 섭렵하는 오일러 경로(Path) 와 제자리로 아름답게 복귀하는 오일러 회로(Circuit) 의 아키텍처 차이를 구별합니다.

2. 한붓그리기의 치명적 규칙 (Rule of the Game)

펜을 종이에 대고 난 뒤 눈사람이든 뭐든 그리기 시작해서, “펜을 절대 종이에서 떼지 않고”, “이미 그려 지나간 길(선)을 두 번 겹쳐 지나지 않으면서” 도형의 모든 선을 완벽하게 완성해 낼 수 있는가를 알아보는 놀이가 바로 한붓그리기입니다.

이 유치해 보이는 놀이를 그랜드마스터 오일러는 ‘그래프(Graph)의 선통과 탐색 알고리즘’ 이라는 거창한 컴퓨터 과학 문제로 정의했습니다.

3. 통과점의 생존 법칙 (짝수점의 진가)

우리가 연필을 들고 어떤 중간 도시 거점(점)을 무사히 관통해 지나가려면 무슨 일이 벌어져야 할까요?

  1. 내 연필이 그 점으로 진입합니다 (In!) $\rightarrow$ 한 번 그렸으니 못 쓰는 선 1가닥 소모.
  2. 내 연필이 그 점에서 탈출합니다 (Out!) $\rightarrow$ 한 번 그렸으니 못 쓰는 선 1가닥 소모.

결국 어떤 ‘중간 거점 역’을 무사히 통과하기 위해서는 무조건 연필선이 2개씩 세트(쌍) 로 묶여서 소모되어야 합니다! (진입선 1개 + 탈출선 1개) 따라서 내 도시(점)에 뚫린 길의 개수인 차수(Degree) 가 2, 4, 6… 같은 [짝수점] 이라면, 연필 궤적은 이 도시를 백날천날 들락날락해도 갇히지 않고 평화롭게 한붓그리기를 이어나갈 수 있습니다.

[홀수점의 저주] 하지만 내 도시에 난 길(차수)이 3개인 늪지대 [홀수점] 이라면?

  • (1회차 방문) : In(1) $\rightarrow$ Out(1) 무사 통과. 남은 길 1개.
  • (2회차 방문) : 빙빙 돌다 다시 In(1)! $\rightarrow$ ERROR! 나갈 탈출구가 다 떨어짐!! 연필 갇힘!! 게임 오버!!

정답이 나왔습니다. 그래프에서 ‘홀수점’ 이 존재하게 되면, 그 점은 중간에 스무스하게 타고 통과할 수가 없고 무조건 연필을 최초로 찍는 ‘출발점’ 이거나 연필이 강제로 마지막에 갇혀 죽어버리는 ‘도착점’ 딱 2가지 역할로 밖에는 못 씁니다.

4. 오일러의 최종 심판 두 가지

이 완벽무결한 논리를 근거로, 그래프가 어떤 형태를 띠든 한붓그리기가 가능한지 1초 만에 렌더링 스캔해 내는 [오일러의 정리] 가 반포되었습니다.

🛡️ 1단계 승리: 오일러 경로 (Eulerian Path)

  • 미션: “모든 길을 한 번씩 밟되, 출발한 곳으로 안 돌아오고 다른 데서 끝나도 인정해 줄게!” (열린 한붓그리기)
  • 오일러 판독 조건: 그래프 전체에 홀수점의 개수가 정확히 양방향 ‘2개’ 일 것. (나머지 점은 모조리 짝수점)
  • 알고리즘: 하나뿐인 홀수점 A에서 펜을 출발시켜 온 동네 짝수점을 헤집고 다니다가, 구조상 남은 단 하나의 홀수점 B에 박히면서 종결처리됨!

👑 2단계 궁극의 승리: 오일러 회로 (Eulerian Circuit)

  • 미션: “모든 길을 다 한 번씩 지나면서, 반드시 맨 처음 펜을 출발했던 그 원점 위치로 귀환 하여 사이클(Circuit) 링을 닫을 것!!” (닫힌 한붓그리기)
  • 오일러 판독 조건: 그래프 전체에 홀수점이 ‘단 0개 (존재하지 않음)’ 여야만 함. (모든 점이 100% 짝수점 방어막 구비)
  • 알고리즘: 모든 거점이 진입+탈출 짝꿍 쉴드를 보유하고 있어 어디서 어떻게 시작하고 돌든, 반드시 길을 다 소모하며 본진 파킹이 가능해 무결점 링(Ring)이 시연됨.

(기억하시나요? 전 챕터 쾨니히스베르크의 7개 다리는 홀수점이 무려 4개라서 게임 오버 오류를 뿜어낸 것입니다.)

5. 현대 도시의 혈관 배선

이 오일러 회로 논리는 “우편 배달부, 제설 차량, 쓰레기 수거 차량” 등 100곳의 도로 골목(선)을 빼먹지 않고 다 훑으면서 본부 주차장(점)으로 기름(비용) 낭비 없이 되돌아와야 하는 도시 노선망 최적화 알고리즘 에 지금 이 순간에도 그대로 사용되고 있습니다.

6. 학습 정리 (Summary)

  1. 홀수점에 의한 통과 제한: 짝수 방향의 길이 뚫린 거점은 무제한 루트 통과가 자유롭지만, 홀수 방향이 뚫린 거점은 ‘IN 하나, OUT 제로’ 구조를 강제하므로 도착 혹은 최초 출발 노드로 제한됩니다.
  2. 오일러 회로(Eulerian Circuit) 판독: 수만 개의 점이 모인 서울 도로망이라도 파이썬으로 연결 스탯을 스캔하여 ‘홀수점이 단 하나도 없는 100% 짝수화 네트워크’임이 확정된다면, 무조건 빙글 돌아 출발지로 복귀 가능한 무결점 한붓그리기 운행 플랜이 존재합니다.
서브목차