직관 — 방이 아니라 복도를 모두 지난다
청소 로봇이 모든 복도를 한 번씩 지나야 한다고 하자. 같은 방을 여러 번 통과해도 되지만 같은 복도를 두 번 청소하지는 않는다. 출발한 방으로 돌아와야 하는지, 다른 방에서 멈춰도 되는지에 따라 가능한 동선이 달라진다.
방을 꼭짓점, 양방향 복도를 변으로 나타낸 가상 단순 그래프다. 복도 길이의 합을 최소화하는 문제가 아니라, 각 변을 정확히 한 번 쓸 수 있는가를 묻는다. 펜을 떼지 않고 같은 선을 두 번 긋지 않는 한붓그리기가 바로 이 질문이다.
오일러 경로는 모든 변을 정확히 한 번 쓴다
오일러 경로는 그래프의 모든 변을 정확히 한 번 지나는 경로다. 그중 출발점으로 돌아오는 것을 오일러 회로라 하고, 이를 갖는 연결그래프를 오일러그래프(Eulerian graph)라 한다. 경로에서 같은 꼭짓점을 다시 만나는 것은 허용한다.
변이 하나 이상 있는 유한한 단순 무방향그래프에서, 고립점을 제외한 부분이 연결되어 있다고 하자. 홀수 차수 꼭짓점의 수를 라고 하면 다음 판정이 성립한다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 그래프 | graph | 유한한 단순 무방향그래프 | |
| 차수 | degree | 꼭짓점 에 닿은 변 수 | |
| 홀수 차수 꼭짓점 수 | number of odd-degree vertices | 차수가 홀수인 점의 개수 | |
| 변 수 | number of edges | 오일러 경로에서 사용할 변의 총수 |
우리교과서의 경로(trail)와 회로(circuit)라는 말을 따른다. 영어 자료에서 Euler path라고도 하지만, 이때 path는 꼭짓점을 반복하지 않는 단순경로라는 뜻이 아니다. 고립점은 사용할 변이 없으므로 ‘모든 변을 지나는 동선’에는 영향을 주지 않는다. 다만 오일러그래프라는 이름은 이 글에서 연결그래프에 사용한다.
홀수 차수 꼭짓점 두 개가 왜 양 끝이 될까?
중간에 도착한 방에서 다시 나가려면 들어온 변과 나간 변이 짝을 이룬다. 출발·도착이 같은 회로에서는 모든 꼭짓점의 사용 변이 짝을 이루므로 차수가 모두 짝수여야 한다. 열린 경로에서는 출발점의 나가는 변 하나와 도착점의 들어오는 변 하나만 짝 없이 남으므로 두 점의 차수는 홀수다.
가상 전시실의 변을 로 두면 차수는 차례로 이다. 차수 합은 10이고 홀수 차수 점은 두 개다. 다음 동선은 다섯 변을 실제로 한 번씩 쓴다.
변 목록은 다. 꼭짓점 를 두 번 만나도 변을 되풀이하지 않았다. 시작을 로 정하면 이런 열린 오일러 경로를 만들 수 없으며, 나 에서 시작해야 한다.
여기에 변 를 추가하면 두 홀수 차수가 각각 1 늘어 모두 짝수가 된다. 그러면 가 오일러 회로다. 그림 1의 각 변에 쓴 순서 번호를 따라가면 된다.
figures/euler_routes.py한붓그리기가 되는지 어떻게 바로 판정할까?
차수만 세면 바로 판정할 수 있다. 변이 있는 부분이 연결되어 있는지 먼저 보고, 홀수 차수 꼭짓점의 수 를 센 뒤 아래 표를 읽는다.
| 홀수 차수 점의 수 | 모든 변을 한 번씩 지나는 동선 | 출발점과 끝점 |
|---|---|---|
| 0 | 오일러 회로가 있다 | 변이 닿은 아무 점에서 출발해 그 점으로 돌아온다 |
| 2 | 열린 오일러 경로만 있다 | 한 홀수 점에서 출발해 다른 홀수 점에서 끝난다 |
| 4 이상 | 없다 | — |
꼭짓점의 차수의 악수 정리에 따라 는 언제나 짝수다. 그래서 가 1이나 3인 그래프는 없고, 표의 세 줄이 모든 경우다.
그림 2 위는 사각형 에 대각선 둘을 그은 그래프다. 네 꼭짓점의 차수가 모두 3이라 이므로 어디서 시작해도 한붓그리기가 안 된다. 여기에 지붕 를 얹어 , 를 그으면 , 의 차수가 4가 되어 다. 그림 2 아래처럼 홀수 점 에서 출발해 에서 끝내면 여덟 변을 한 번씩 지난다.
figures/house_puzzle.py대각선이 엇갈리는 점에서 방향을 꺾을 수 있다고 보아 그 점을 꼭짓점으로 넣어도 결론은 같다. 그 점의 차수는 4라서 홀수 차수 점의 수가 바뀌지 않는다.
차수 조건이 충분하다는 것은 어떻게 알까?
모든 차수가 짝수인 연결 부분에서 시작해, 아직 쓰지 않은 변을 따라 더 갈 수 없을 때까지 간다. 시작점 이외에서는 들어온 변 뒤에 짝이 될 나가는 변이 남으므로 중간점에서 멈출 수 없다. 결국 출발점으로 돌아온 닫힌 경로를 얻는다.
남은 변이 있다면 연결성 때문에 지금 경로의 꼭짓점 중 하나가 아직 쓰지 않은 변과 연결된다. 그 점에서 같은 방법으로 새 닫힌 경로를 만들고 기존 경로 사이에 끼워 넣는다. 이미 쓴 변은 새 경로에 쓰지 않는다. 변의 수가 유한하므로 반복하면 모든 변을 포함한 회로가 완성된다.
그림 3은 모든 차수가 4인 (다섯 점을 모두 서로 이은 그래프)에서 이 과정을 보인다. 첫 닫힌 경로 는 다섯 변만 쓰고 멈춘다. 남은 다섯 변에서는 각 점의 차수가 2이므로 에서 출발해 로 돌아오는 를 만들 수 있다. 이것을 첫 경로의 자리에 끼워 넣으면 열 변을 모두 쓴다.
figures/splice_circuits.py홀수 차수 점이 둘이면 그중 하나에서 출발한다. 같은 짝 논증에 따라 처음 멈추는 점은 다른 홀수 점이어야 한다. 이 열린 경로를 사용하고 나면 남은 변에 대한 각 점의 차수는 짝수다. 남은 변이 있는 부분마다 닫힌 경로를 만들어 끼워 넣으면 모든 변을 포함한 열린 경로가 된다.
반대로 떨어진 삼각형 두 개는 모든 차수가 2지만 한 동선으로 건너갈 방법이 없다. 차수만 세고 연결성을 생략해서는 안 된다.
쾨니히스베르크 다리 문제는 왜 불가능할까?
네 땅에 놓인 다리 수가 모두 홀수여서 홀수 차수 점이 4개이기 때문이다. 옛 도시 쾨니히스베르크에서는 강이 섬 와 세 땅 를 나누고, 다리 일곱 개가 이들을 이었다. 일곱 다리를 한 번씩만 건너는 산책로가 있는지를 18세기에 오일러가 이렇게 따졌다.
땅을 꼭짓점, 다리를 변으로 두면 와 사이에 다리가 두 개라 중복 변이 생긴다. 이 단원의 단순 그래프로 나타내려면 다리마다 가운데에 점을 하나 찍어 변 두 개로 나눈다. 가운데 점은 들어가고 나오는 차수 2라서 홀짝 판정을 바꾸지 않는다.
figures/konigsberg_bridges.py그림 4에서 땅의 차수는 가 5, 가 3이다. 홀수 차수 점이 4개이므로 식 (1)에 따라 열린 경로도 회로도 없다. 와 사이에 다리를 하나 더 놓으면 두 땅의 차수가 4가 되어 이고, 에서 출발해 에서 끝나는 산책로가 생긴다.
홀수 차수 점이 4개 이상이면 몇 번 다시 지나야 할까?
홀수 차수 점이 개이면 열린 동선은 적어도 번, 닫힌 동선은 적어도 번 복도를 다시 지나야 한다. 청소 로봇처럼 모든 복도를 꼭 지나야 하는데 한붓그리기가 안 될 때 쓰는 계산이다.
같은 변을 한 번 더 지나면 그 두 끝점에서 지나는 횟수가 1씩 늘어 두 점의 홀짝이 함께 바뀐다. 그래서 변 하나를 한 번 다시 지나도 홀수 점은 많아야 2개 줄어든다. 열린 동선은 홀수 점 2개를 양 끝으로 남겨도 되고, 닫힌 동선은 하나도 남기면 안 되므로 다음 하한을 얻는다.
그림 2 위의 사각형은 이므로 열린 동선은 1번, 닫힌 동선은 2번 이상 다시 지나야 한다. 실제로 는 변 만 다시 지나 일곱 걸음에 여섯 변을 모두 지난다. 는 와 를 다시 지나 여덟 걸음 만에 출발점으로 돌아온다. 같은 변을 반복하므로 둘 다 경로가 아니라 보행이다.
오일러그래프는 모든 변을 한 번씩 도는 회로가 있는 연결그래프다. 변이 있는 연결 부분의 홀수 차수 점이 0개면 회로, 2개면 열린 오일러 경로가 있고, 4개 이상이면 한붓그리기가 안 된다.
오일러그래프에서는 아무 점에서 시작해도 되나요?
변이 있는 연결된 오일러그래프라면 어느 꼭짓점에서든 회로를 시작할 수 있다. 닫힌 동선의 읽기 시작 위치를 바꾸면 되기 때문이다. 열린 경로만 있는 경우에는 두 홀수 차수 점 중 하나에서 시작해야 한다.
고립점이 있으면 모든 변 순회가 불가능한가요?
변이 있는 부분만 연결되어 있으면 가능할 수 있다. 삼각형 옆에 고립점 하나를 추가해도 삼각형의 세 변 순회는 그대로다. 다만 모든 꼭짓점을 방문하라는 다른 문제라면 고립점도 고려해야 한다.
오일러 회로와 해밀턴 회로는 무엇이 다른가요?
오일러 회로는 모든 변을, 해밀턴 회로는 모든 꼭짓점을 정확히 한 번씩 지나는 회로다. 그림 1 아래 그래프에는 오일러 회로 가 있지만, 꼭짓점 를 두 번 지나야 하므로 해밀턴 회로는 없다. 자세한 비교는 해밀턴그래프에서 다룬다.
오일러그래프의 흔한 오해
- 꼭짓점을 다시 지나면 실패다. — 오일러 문제는 변의 사용 횟수 조건이다. 그림 1의 재방문은 허용된다.
- 홀수 차수 점이 4개여도 출발점을 잘 고르면 된다. — 열린 동선의 끝은 둘뿐이므로 네 홀수 점의 짝 없는 변을 모두 수용할 수 없다. 그림 2 위의 사각형은 어느 점에서 출발해도 실패한다.
직접 해보기
- 꼭짓점 의 네 변 에 변 을 추가했다. 열린 오일러 경로를 하나 쓰시오.
- 중심 에 잎 을 각각 잇는 세 변만 있다. 한 번씩 모두 지날 수 있는가?
- 삼각형 두 개가 서로 떨어져 있다. 홀수 차수 점의 수와 오일러 회로 존재 여부를 비교하시오.
- 문제 1에서 모든 변을 한 번씩 지나는 닫힌 동선도 가능한지 설명하시오.
- 꼭짓점 6개를 모두 서로 이은 와 7개를 모두 이은 에 각각 오일러 회로나 열린 오일러 경로가 있는지 판정하시오.
답과 풀이
- 차수는 라서 이 양 끝이다. 은 을 한 번씩 쓰는 길이 5의 경로다.
- 차수는 중심이 3, 잎이 각각 1이다. 홀수 차수 점이 4개라서 불가능하다.
- 홀수 차수 점은 0개지만 변이 있는 부분이 두 덩어리다. 한 번의 동선으로 전부 지나지 못한다.
- 불가능하다. 의 차수가 홀수이므로 출발점으로 돌아오면서 각 점에서 들어옴·나감을 모두 짝지을 수 없다.
- 의 각 점은 나머지 5개와 이어져 차수가 5이므로 이다. 회로도 열린 경로도 없다. 의 차수는 모두 6이고 연결되어 있으므로 오일러 회로가 있다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-05]의 오일러그래프 범위.
- Levin, Euler Paths and Circuits — 차수의 짝짓기와 닫힌 동선 끼워 넣기. 연결 가정을 확인하고 단순 그래프 예제로 재구성했다.
- 우리교과서 이산 수학 — 인쇄143쪽의 경로·회로 관례와 로봇 청소기 도입을 따른다. 역사적 다리 그림의 중복 변은 본문에서 다리마다 점을 넣어 단순 그래프로 바꿨다.
- Buckingham, Graph Theory — 2.6 「Euler circuits and Euler trails」에서 짝수 차수 조건의 증명과 동선 찾기를 대조했다.
영상 노트
- 00:00 청소 동선에서 방 재방문과 복도 재사용 구별하기
- 00:45 식 (2)의 변을 하나씩 지우며 사용 목록 확인하기
- 01:20 차수의 짝짓기로 식 (1)의 필요조건 설명하기
- 02:00 판정 표로 그림 2의 사각형과 집 모양 한붓그리기 비교하기
- 02:50 그림 3처럼 닫힌 경로를 끼워 넣어 식 (3) 완성하기
- 03:40 쾨니히스베르크 다리에 점을 넣어 차수 5, 3, 3, 3 세기
- 04:20 식 (4)로 다시 지나야 하는 최소 횟수 구하기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 한붓그리기 판정 표와 집 모양 비교, 닫힌 경로 끼워 넣기 과정, 쾨니히스베르크 다리 문제, 다시 지나야 하는 최소 횟수 절 추가, 변 없는 그래프 질문을 오일러·해밀턴 차이 질문으로 교체, 해보기 5번 추가 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림