# 그래프와 오일러 경로

분야: CS·데이터사이언스
학교급: 중등
교육과정: 정규 교육과정 외 — 점과 선의 연결 관계만 남긴 구조. 쾨니히스베르크 다리 문제에서 시작됐다.
정식 URL: https://pi.devxdev.xyz/wiki/math/%EA%B7%B8%EB%9E%98%ED%94%84%EC%99%80_%EC%98%A4%EC%9D%BC%EB%9F%AC_%EA%B2%BD%EB%A1%9C

---

<!-- prereq: 다각형 -->
> 이 개념은 정규 교육과정 밖의 내용으로, 도형의 길이나 각도는 다 지우고 점과 선의 연결 관계만 남긴 구조를 다루며, 쾨니히스베르크 다리 문제에서 출발했다.

## 정의

그래프(graph)는 점(꼭짓점, vertex)들과 그 점들을 잇는 선(변, edge)들로만 이루어진 구조다. 도형의 모양·길이·각도는 신경 쓰지 않고, "어떤 점과 어떤 점이 연결되어 있는가"라는 관계만 남긴다.

한 꼭짓점에 연결된 변의 개수를 그 꼭짓점의 **차수**(次數, degree)라고 한다. 꼭짓점 $A$의 차수는 $\deg(A)$(디그리 에이라고 읽는다)로 나타내기도 한다.

그래프의 **모든 변을 딱 한 번씩만** 지나가는 경로를 **오일러 경로**(Euler path)라 하고, 출발점과 도착점이 같은 오일러 경로를 **오일러 회로**(Euler circuit)라고 한다. "한붓그리기가 가능한가"라는 질문이 바로 오일러 경로가 존재하는지를 묻는 것이다.

## 직관

지도에서 땅을 점으로, 다리를 선으로 바꿔 그린다고 생각하면 된다. 땅의 크기나 다리의 길이는 다 지워지고, "몇 개의 다리가 어느 땅과 어느 땅을 잇는가"만 남는다. 그러면 "종이에서 연필을 떼지 않고 모든 선을 한 번씩만 그릴 수 있는가"라는, 눈으로 바로 확인하기 힘든 문제가 남는다.

## 유도

한붓그리기를 여러 도형으로 시도해 보면 어떤 것은 되고 어떤 것은 안 된다. 왜 그런지 따져 보자.

**1단계.** 경로가 어떤 꼭짓점을 그냥 지나쳐 갈 때(시작점도 끝점도 아닐 때), 그 꼭짓점에서는 변 하나로 들어와서 다른 변 하나로 나간다. 즉 그 꼭짓점을 한 번 지나칠 때마다 변을 정확히 2개씩 소모한다.

**2단계.** 그러므로 시작점·끝점이 아닌 꼭짓점은 연결된 변의 개수(차수)가 항상 짝수여야 한다. 홀수라면 마지막에 변 하나가 남아서 그 점을 완전히 빠져나올 수 없다.

**3단계.** 시작점은 예외다. 처음 나갈 때 변 하나를 더 쓰기 때문에, 시작점의 차수는 (지나칠 때 쓰는 짝수 개) + (처음 나가는 1개)로 홀수가 될 수 있다. 끝점도 마찬가지로 (마지막에 들어오는 1개)가 더해져 홀수가 될 수 있다. 단, 시작점과 끝점이 같아서 회로를 이루면 그 점도 다시 짝수여야 한다.

**4단계.** 정리하면: 홀수 차수인 꼭짓점은 경로의 시작점과 끝점, 최대 2개뿐이어야 한다. 그러므로
- 홀수 차수 꼭짓점이 **0개**면 → 아무 점에서 출발해도 같은 점으로 돌아오는 **오일러 회로**가 존재한다.
- 홀수 차수 꼭짓점이 **정확히 2개**면 → 그 두 점을 각각 시작점·끝점으로 하는 **오일러 경로**가 존재한다.
- 홀수 차수 꼭짓점이 **3개 이상**이면 → 오일러 경로 자체가 존재하지 않는다.

**5단계.** 쾨니히스베르크 다리 문제에 적용해 보면, 4개의 땅에 각각 차수 5, 3, 3, 3인 다리가 연결되어 있었다(홀수 차수 땅이 4개). 4단계의 결론에 따라 오일러 경로조차 존재하지 않으므로, "모든 다리를 한 번씩만 건너서 돌아오는 것"은 애초에 불가능하다.

## 예시

꼭짓점 $A,B,C,D$에 변 $AB, BC, CD, DA, AC$(대각선 하나 포함)가 있는 그래프를 생각하자.

차수를 세면 $\deg(A)=3$ (AB, DA, AC), $\deg(B)=2$ (AB, BC), $\deg(C)=3$ (BC, CD, AC), $\deg(D)=2$ (CD, DA)다. 홀수 차수인 점은 $A, C$ 두 개뿐이므로 오일러 경로가 존재하며, $A$에서 시작해 $C$에서 끝나야 한다.

실제 경로: $A \to B \to C \to D \to A \to C$ — $AB, BC, CD, DA, AC$ 다섯 변을 정확히 한 번씩 사용했다.

## 🌍 실생활 예시

제설차나 쓰레기 수거차가 마을의 모든 도로(변)를 한 번씩만 지나면서 순찰하려는 경로 계획이 오일러 경로 문제 그 자체다. 도로 교차점을 꼭짓점, 도로를 변으로 바꾼 뒤 홀수 차수 교차점의 개수를 세어 보면, 기름을 낭비하며 같은 길을 두 번 지나지 않고 한 번에 순찰을 마칠 수 있는지 미리 알 수 있다.

## ⚠️ 흔한 실수

- **다중 변을 하나로 뭉뚱그려 센다** → 쾨니히스베르크처럼 두 땅 사이에 다리(변)가 2개 있으면 차수에도 2번 반영해야 한다. 하나로 세면 차수가 틀려서 결론이 뒤바뀐다.
- **"홀수 차수 점이 짝수 개면 항상 된다"고 착각한다** → 4개, 6개도 개수로는 짝수지만 오일러 경로는 홀수 차수 점이 정확히 0개이거나 2개일 때만 존재한다. 4개면 불가능하다.
- **변 기준과 점 기준을 혼동한다** → 오일러 경로는 "변을 한 번씩" 지나는 것이지 "점을 한 번씩" 방문하는 것이 아니다. 같은 꼭짓점을 여러 번 지나가도 전혀 문제없다.

## 확인 문제

1. (개념을 다지는 문제) 쾨니히스베르크 다리 문제에서 새로운 다리를 딱 1개 놓아서 오일러 경로가 가능하도록 만들려면, 어느 두 땅 사이에 놓아야 할까? 그 이유도 설명하라.
2. 꼭짓점 $A,B,C,D$와 변 $AB, BC, CD, DA$만 있는 사각형 그래프의 각 꼭짓점 차수를 구하고, 오일러 회로가 존재하는지 판단하라.
3. "예시" 섹션의 그래프에서 오일러 경로는 반드시 $A$나 $C$에서 시작해야 하고 $B$나 $D$에서 시작하면 안 되는 이유를 차수를 이용해 설명하라.

정답 보기:

1. 원래 4개의 땅 모두 차수가 홀수(5, 3, 3, 3)였다. 이 중 서로 다른 두 땅 사이에 새 다리를 놓으면 그 두 땅의 차수가 각각 1씩 늘어 짝수가 되므로, 홀수 차수인 땅이 4개에서 2개로 줄어 오일러 경로가 가능해진다.
2. $\deg(A)=\deg(B)=\deg(C)=\deg(D)=2$로 모두 짝수다. 홀수 차수 점이 0개이므로 오일러 회로가 존재한다. 예: $A \to B \to C \to D \to A$.
3. $A$와 $C$만 차수가 홀수(3)이고 $B, D$는 차수가 짝수(2)다. 경로의 시작점·끝점만 홀수 차수를 가질 수 있으므로, $B$나 $D$에서 출발하면 도중에 반드시 변 하나가 남아 그 점을 완전히 빠져나오지 못한다.



## 📜 역사

1736년 레온하르트 오일러는 쾨니히스베르크(현재 러시아 칼리닌그라드)의 7개 다리를 한 번씩만 건너 원래 자리로 돌아올 수 있는지를 묻는 문제를 풀었다. 그는 땅의 모양이나 다리의 길이를 모두 무시하고 "어느 땅과 어느 땅이 다리로 연결되어 있는가"라는 관계만 남긴 그림으로 문제를 바꾸었는데, 이것이 최초의 그래프였다. 그는 각 땅에 연결된 다리 수(차수)가 홀수인 땅이 몇 개인지에 따라 답이 결정된다는 것을 밝혀, 이 문제가 불가능함을 증명했다. 이 연구가 오늘날 그래프 이론이라 불리는 수학 분야의 출발점이 되었다.

## 관련 개념

- 다각형 — 꼭짓점과 변이라는 용어를 먼저 익히는 곳
- 경우의 수 — 여러 경로·연결 방법을 따지는 조합적 사고를 공유
- 재귀 알고리즘 — 오일러 경로·회로를 실제로 찾는 알고리즘에서 쓰이는 탐색 방식

---

관련 개념:
- 다각형 (/wiki/math/%EB%8B%A4%EA%B0%81%ED%98%95)
- 경우의 수 (/wiki/math/%EA%B2%BD%EC%9A%B0%EC%9D%98_%EC%88%98)
- 재귀 알고리즘 (/wiki/math/%EC%9E%AC%EA%B7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)