기초수학오일러그래프#358

오일러그래프

Eulerian Graphs

오일러그래프는 모든 변을 정확히 한 번 지나는 회로가 있는 연결그래프다. 변이 있는 부분의 연결성을 확인한 뒤 홀수 차수 꼭짓점의 개수로 닫힌 순회와 열린 순회, 곧 한붓그리기의 가능성을 판정하고 쾨니히스베르크 다리 문제에 적용한다.

읽는 시간
약 8분
선수 개념
꼭짓점의 차수

직관 — 방이 아니라 복도를 모두 지난다

직관

청소 로봇이 모든 복도를 한 번씩 지나야 한다고 하자. 같은 방을 여러 번 통과해도 되지만 같은 복도를 두 번 청소하지는 않는다. 출발한 방으로 돌아와야 하는지, 다른 방에서 멈춰도 되는지에 따라 가능한 동선이 달라진다.

방을 꼭짓점, 양방향 복도를 변으로 나타낸 가상 단순 그래프다. 복도 길이의 합을 최소화하는 문제가 아니라, 각 변을 정확히 한 번 쓸 수 있는가를 묻는다. 펜을 떼지 않고 같은 선을 두 번 긋지 않는 한붓그리기가 바로 이 질문이다.

오일러 경로는 모든 변을 정확히 한 번 쓴다

오일러 경로는 그래프의 모든 변을 정확히 한 번 지나는 경로다. 그중 출발점으로 돌아오는 것을 오일러 회로라 하고, 이를 갖는 연결그래프를 오일러그래프(Eulerian graph)라 한다. 경로에서 같은 꼭짓점을 다시 만나는 것은 허용한다.

변이 하나 이상 있는 유한한 단순 무방향그래프에서, 고립점을 제외한 부분이 연결되어 있다고 하자. 홀수 차수 꼭짓점의 수를 oo라고 하면 다음 판정이 성립한다.

오일러 회로가 존재  ⟺  o=0,출발점과 끝점이 다른 오일러 경로가 존재  ⟺  o=2.(1)\begin{aligned} \text{오일러 회로가 존재}&\iff o=0,\\ \text{출발점과 끝점이 다른 오일러 경로가 존재}&\iff o=2. \end{aligned} \tag{1}
정의
기호이름원어뜻
G=(V,E)G=(V,E)그래프graph유한한 단순 무방향그래프
deg⁡(v)\deg(v)차수degree꼭짓점 vv에 닿은 변 수
oo홀수 차수 꼭짓점 수number of odd-degree vertices차수가 홀수인 점의 개수
mm변 수number of edges오일러 경로에서 사용할 변의 총수

우리교과서의 경로(trail)와 회로(circuit)라는 말을 따른다. 영어 자료에서 Euler path라고도 하지만, 이때 path는 꼭짓점을 반복하지 않는 단순경로라는 뜻이 아니다. 고립점은 사용할 변이 없으므로 ‘모든 변을 지나는 동선’에는 영향을 주지 않는다. 다만 오일러그래프라는 이름은 이 글에서 연결그래프에 사용한다.

홀수 차수 꼭짓점 두 개가 왜 양 끝이 될까?

중간에 도착한 방에서 다시 나가려면 들어온 변과 나간 변이 짝을 이룬다. 출발·도착이 같은 회로에서는 모든 꼭짓점의 사용 변이 짝을 이루므로 차수가 모두 짝수여야 한다. 열린 경로에서는 출발점의 나가는 변 하나와 도착점의 들어오는 변 하나만 짝 없이 남으므로 두 점의 차수는 홀수다.

가상 전시실의 변을 AB,AC,BC,CD,DEAB,AC,BC,CD,DE로 두면 차수는 차례로 2,2,3,2,12,2,3,2,1이다. 차수 합은 10이고 홀수 차수 점은 C,EC,E 두 개다. 다음 동선은 다섯 변을 실제로 한 번씩 쓴다.

E→D→C→A→B→C.(2)E\to D\to C\to A\to B\to C. \tag{2}

변 목록은 ED,DC,CA,AB,BCED,DC,CA,AB,BC다. 꼭짓점 CC를 두 번 만나도 변을 되풀이하지 않았다. 시작을 AA로 정하면 이런 열린 오일러 경로를 만들 수 없으며, CC나 EE에서 시작해야 한다.

여기에 변 CECE를 추가하면 두 홀수 차수가 각각 1 늘어 모두 짝수가 된다. 그러면 C,A,B,C,D,E,CC,A,B,C,D,E,C가 오일러 회로다. 그림 1의 각 변에 쓴 순서 번호를 따라가면 된다.

위는 식 (2)의 열린 오일러 경로, 아래는 CE를 추가한 오일러 회로다. 변 위 숫자는 지나가는 순서이며, 같은 꼭짓점 C를 다시 만나도 같은 변을 반복하지 않는다.
그림 1 위는 식 (2)의 열린 오일러 경로, 아래는 CE를 추가한 오일러 회로다. 변 위 숫자는 지나가는 순서이며, 같은 꼭짓점 C를 다시 만나도 같은 변을 반복하지 않는다. figures/euler_routes.py

한붓그리기가 되는지 어떻게 바로 판정할까?

차수만 세면 바로 판정할 수 있다. 변이 있는 부분이 연결되어 있는지 먼저 보고, 홀수 차수 꼭짓점의 수 oo를 센 뒤 아래 표를 읽는다.

홀수 차수 점의 수 oo모든 변을 한 번씩 지나는 동선출발점과 끝점
0오일러 회로가 있다변이 닿은 아무 점에서 출발해 그 점으로 돌아온다
2열린 오일러 경로만 있다한 홀수 점에서 출발해 다른 홀수 점에서 끝난다
4 이상없다—

꼭짓점의 차수의 악수 정리에 따라 oo는 언제나 짝수다. 그래서 oo가 1이나 3인 그래프는 없고, 표의 세 줄이 모든 경우다.

그림 2 위는 사각형 FGHJFGHJ에 대각선 둘을 그은 그래프다. 네 꼭짓점의 차수가 모두 3이라 o=4o=4이므로 어디서 시작해도 한붓그리기가 안 된다. 여기에 지붕 KK를 얹어 JKJK, HKHK를 그으면 JJ, HH의 차수가 4가 되어 o=2o=2다. 그림 2 아래처럼 홀수 점 FF에서 출발해 GG에서 끝내면 여덟 변을 한 번씩 지난다.

위는 사각형 FGHJ에 대각선 둘을 그은 그래프, 아래는 지붕 K를 얹은 집 모양이다. 주황 테두리가 홀수 차수 점이고 옆의 숫자가 차수다. 아래 변 위의 숫자는 F에서 출발해 G에서 끝나는 한붓그리기의 순서다.
그림 2 위는 사각형 FGHJ에 대각선 둘을 그은 그래프, 아래는 지붕 K를 얹은 집 모양이다. 주황 테두리가 홀수 차수 점이고 옆의 숫자가 차수다. 아래 변 위의 숫자는 F에서 출발해 G에서 끝나는 한붓그리기의 순서다. figures/house_puzzle.py

대각선이 엇갈리는 점에서 방향을 꺾을 수 있다고 보아 그 점을 꼭짓점으로 넣어도 결론은 같다. 그 점의 차수는 4라서 홀수 차수 점의 수가 바뀌지 않는다.

차수 조건이 충분하다는 것은 어떻게 알까?

모든 차수가 짝수인 연결 부분에서 시작해, 아직 쓰지 않은 변을 따라 더 갈 수 없을 때까지 간다. 시작점 이외에서는 들어온 변 뒤에 짝이 될 나가는 변이 남으므로 중간점에서 멈출 수 없다. 결국 출발점으로 돌아온 닫힌 경로를 얻는다.

남은 변이 있다면 연결성 때문에 지금 경로의 꼭짓점 중 하나가 아직 쓰지 않은 변과 연결된다. 그 점에서 같은 방법으로 새 닫힌 경로를 만들고 기존 경로 사이에 끼워 넣는다. 이미 쓴 변은 새 경로에 쓰지 않는다. 변의 수가 유한하므로 반복하면 모든 변을 포함한 회로가 완성된다.

그림 3은 모든 차수가 4인 K5K_5(다섯 점을 모두 서로 이은 그래프)에서 이 과정을 보인다. 첫 닫힌 경로 A,B,C,D,E,AA,B,C,D,E,A는 다섯 변만 쓰고 멈춘다. 남은 다섯 변에서는 각 점의 차수가 2이므로 CC에서 출발해 CC로 돌아오는 C,E,B,D,A,CC,E,B,D,A,C를 만들 수 있다. 이것을 첫 경로의 CC 자리에 끼워 넣으면 열 변을 모두 쓴다.

A→B→C→E→B→D→A→C→D→E→A.(3)A\to B\to C\to E\to B\to D\to A\to C\to D\to E\to A. \tag{3}
모든 차수가 4인 K₅에서 위는 첫 닫힌 경로 A, B, C, D, E, A(번호 1~5)이고 점선이 남은 변이다. 아래는 남은 변으로 만든 C, E, B, D, A, C를 C 자리에 끼워 넣은 오일러 회로의 순서다.
그림 3 모든 차수가 4인 K₅에서 위는 첫 닫힌 경로 A, B, C, D, E, A(번호 1~5)이고 점선이 남은 변이다. 아래는 남은 변으로 만든 C, E, B, D, A, C를 C 자리에 끼워 넣은 오일러 회로의 순서다. figures/splice_circuits.py

홀수 차수 점이 둘이면 그중 하나에서 출발한다. 같은 짝 논증에 따라 처음 멈추는 점은 다른 홀수 점이어야 한다. 이 열린 경로를 사용하고 나면 남은 변에 대한 각 점의 차수는 짝수다. 남은 변이 있는 부분마다 닫힌 경로를 만들어 끼워 넣으면 모든 변을 포함한 열린 경로가 된다.

반대로 떨어진 삼각형 두 개는 모든 차수가 2지만 한 동선으로 건너갈 방법이 없다. 차수만 세고 연결성을 생략해서는 안 된다.

쾨니히스베르크 다리 문제는 왜 불가능할까?

네 땅에 놓인 다리 수가 모두 홀수여서 홀수 차수 점이 4개이기 때문이다. 옛 도시 쾨니히스베르크에서는 강이 섬 AA와 세 땅 B,C,DB,C,D를 나누고, 다리 일곱 개가 이들을 이었다. 일곱 다리를 한 번씩만 건너는 산책로가 있는지를 18세기에 오일러가 이렇게 따졌다.

땅을 꼭짓점, 다리를 변으로 두면 AA와 BB 사이에 다리가 두 개라 중복 변이 생긴다. 이 단원의 단순 그래프로 나타내려면 다리마다 가운데에 점을 하나 찍어 변 두 개로 나눈다. 가운데 점은 들어가고 나오는 차수 2라서 홀짝 판정을 바꾸지 않는다.

쾨니히스베르크의 섬 A와 땅 B, C, D, 일곱 다리를 그래프로 나타냈다. 회색 띠가 강이고 검은 작은 점은 다리마다 넣은 가운데 점이다. 땅 옆의 숫자가 차수이며 넷 모두 홀수다.
그림 4 쾨니히스베르크의 섬 A와 땅 B, C, D, 일곱 다리를 그래프로 나타냈다. 회색 띠가 강이고 검은 작은 점은 다리마다 넣은 가운데 점이다. 땅 옆의 숫자가 차수이며 넷 모두 홀수다. figures/konigsberg_bridges.py

그림 4에서 땅의 차수는 AA가 5, B,C,DB,C,D가 3이다. 홀수 차수 점이 4개이므로 식 (1)에 따라 열린 경로도 회로도 없다. BB와 CC 사이에 다리를 하나 더 놓으면 두 땅의 차수가 4가 되어 o=2o=2이고, AA에서 출발해 DD에서 끝나는 산책로가 생긴다.

홀수 차수 점이 4개 이상이면 몇 번 다시 지나야 할까?

홀수 차수 점이 oo개이면 열린 동선은 적어도 (o−2)/2(o-2)/2번, 닫힌 동선은 적어도 o/2o/2번 복도를 다시 지나야 한다. 청소 로봇처럼 모든 복도를 꼭 지나야 하는데 한붓그리기가 안 될 때 쓰는 계산이다.

같은 변을 한 번 더 지나면 그 두 끝점에서 지나는 횟수가 1씩 늘어 두 점의 홀짝이 함께 바뀐다. 그래서 변 하나를 한 번 다시 지나도 홀수 점은 많아야 2개 줄어든다. 열린 동선은 홀수 점 2개를 양 끝으로 남겨도 되고, 닫힌 동선은 하나도 남기면 안 되므로 다음 하한을 얻는다.

열린 동선: o−22번,닫힌 동선: o2번.(4)\text{열린 동선: }\frac{o-2}{2}\text{번},\qquad\text{닫힌 동선: }\frac{o}{2}\text{번}. \tag{4}

그림 2 위의 사각형은 o=4o=4이므로 열린 동선은 1번, 닫힌 동선은 2번 이상 다시 지나야 한다. 실제로 H,F,G,H,J,F,G,JH,F,G,H,J,F,G,J는 변 FGFG만 다시 지나 일곱 걸음에 여섯 변을 모두 지난다. F,G,H,J,F,H,G,J,FF,G,H,J,F,H,G,J,F는 GHGH와 JFJF를 다시 지나 여덟 걸음 만에 출발점으로 돌아온다. 같은 변을 반복하므로 둘 다 경로가 아니라 보행이다.

핵심

오일러그래프는 모든 변을 한 번씩 도는 회로가 있는 연결그래프다. 변이 있는 연결 부분의 홀수 차수 점이 0개면 회로, 2개면 열린 오일러 경로가 있고, 4개 이상이면 한붓그리기가 안 된다.

오일러그래프에서는 아무 점에서 시작해도 되나요?

변이 있는 연결된 오일러그래프라면 어느 꼭짓점에서든 회로를 시작할 수 있다. 닫힌 동선의 읽기 시작 위치를 바꾸면 되기 때문이다. 열린 경로만 있는 경우에는 두 홀수 차수 점 중 하나에서 시작해야 한다.

고립점이 있으면 모든 변 순회가 불가능한가요?

변이 있는 부분만 연결되어 있으면 가능할 수 있다. 삼각형 옆에 고립점 하나를 추가해도 삼각형의 세 변 순회는 그대로다. 다만 모든 꼭짓점을 방문하라는 다른 문제라면 고립점도 고려해야 한다.

오일러 회로와 해밀턴 회로는 무엇이 다른가요?

오일러 회로는 모든 변을, 해밀턴 회로는 모든 꼭짓점을 정확히 한 번씩 지나는 회로다. 그림 1 아래 그래프에는 오일러 회로 C,A,B,C,D,E,CC,A,B,C,D,E,C가 있지만, 꼭짓점 CC를 두 번 지나야 하므로 해밀턴 회로는 없다. 자세한 비교는 해밀턴그래프에서 다룬다.

오일러그래프의 흔한 오해

  • 꼭짓점을 다시 지나면 실패다. — 오일러 문제는 변의 사용 횟수 조건이다. 그림 1의 CC 재방문은 허용된다.
  • 홀수 차수 점이 4개여도 출발점을 잘 고르면 된다. — 열린 동선의 끝은 둘뿐이므로 네 홀수 점의 짝 없는 변을 모두 수용할 수 없다. 그림 2 위의 사각형은 어느 점에서 출발해도 실패한다.

직접 해보기

  1. 꼭짓점 P,Q,R,SP,Q,R,S의 네 변 PQ,QR,RS,SPPQ,QR,RS,SP에 변 PRPR을 추가했다. 열린 오일러 경로를 하나 쓰시오.
  2. 중심 OO에 잎 P,Q,RP,Q,R을 각각 잇는 세 변만 있다. 한 번씩 모두 지날 수 있는가?
  3. 삼각형 두 개가 서로 떨어져 있다. 홀수 차수 점의 수와 오일러 회로 존재 여부를 비교하시오.
  4. 문제 1에서 모든 변을 한 번씩 지나는 닫힌 동선도 가능한지 설명하시오.
  5. 꼭짓점 6개를 모두 서로 이은 K6K_6와 7개를 모두 이은 K7K_7에 각각 오일러 회로나 열린 오일러 경로가 있는지 판정하시오.
답과 풀이
  1. 차수는 3,2,3,23,2,3,2라서 P,RP,R이 양 끝이다. P,Q,R,S,P,RP,Q,R,S,P,R은 PQ,QR,RS,SP,PRPQ,QR,RS,SP,PR을 한 번씩 쓰는 길이 5의 경로다.
  2. 차수는 중심이 3, 잎이 각각 1이다. 홀수 차수 점이 4개라서 불가능하다.
  3. 홀수 차수 점은 0개지만 변이 있는 부분이 두 덩어리다. 한 번의 동선으로 전부 지나지 못한다.
  4. 불가능하다. P,RP,R의 차수가 홀수이므로 출발점으로 돌아오면서 각 점에서 들어옴·나감을 모두 짝지을 수 없다.
  5. K6K_6의 각 점은 나머지 5개와 이어져 차수가 5이므로 o=6o=6이다. 회로도 열린 경로도 없다. K7K_7의 차수는 모두 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)로 다시 지나야 하는 최소 횟수 구하기

지도에서의 위치

그래프의 뜻기초수학꼭짓점의 차수기초수학오일러그래프지금 이 페이지해밀턴그래프기초수학
선수 개념
이 페이지
다음 개념
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 한붓그리기 판정 표와 집 모양 비교, 닫힌 경로 끼워 넣기 과정, 쾨니히스베르크 다리 문제, 다시 지나야 하는 최소 횟수 절 추가, 변 없는 그래프 질문을 오일러·해밀턴 차이 질문으로 교체, 해보기 5번 추가 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림