최근 수정 시각 : 2025-07-16 20:22:39

한붓그리기


이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
이론
<colbgcolor=#3CC> 기본 대상 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오(예상과 확인) · 불 논리 · 브라에스 역설 · 포함-배제의 원리
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


1. 개요2. 기원3. 조건
3.1. 꼭짓점의 차수3.2. 꼭짓점 차수가 모두 짝수3.3. 꼭짓점 차수가 2개만 홀수이고 나머지는 모두 짝수3.4. 그 외
4. 고등학교 교육과정5. 응용6. 한붓그리기 게임7. 기타

1. 개요

한붓그리기는 한 번 지나간 선으로는 지나가지 않고 모든 선을 이어 그림을 완성하는 일이다. 붓을 종이에서 떼지 않고 한 번에 그린다고 해서 '한붓그리기'라는 이름이 붙었다.

이산수학에서는 오일러 경로(Euler trail)라 하며, 출발점으로 다시 되돌아오면, 즉 경로가 닫힌 경우 특히 오일러 회로(Euler circuit)이라고 부른다. 비슷한 그래프 이론 문제로는 모든 을 한 번만 지나야 하는 한붓그리기 문제와는 반대로 모든 꼭짓점을 모두 한 번만 방문해야 하는 해밀턴 경로 문제가 있다.

2. 기원

우체부가 쾨니히스베르크에 있는 7개의 다리를 단 한 번씩만 건너서 다시 출발점으로 되돌아올 수 있겠냐는 문제를 1736년에 레온하르트 오일러가 불가능하다고 증명한 것을 한붓그리기의 이론적 출발점으로 보고 있다.

3. 조건

파일:external/upload.wikimedia.org/500px-K%C3%B6nigsberg_graph.svg.png
한붓그리기가 불가능한 것으로 유명한 '쾨니히스베르크 다리 건너기 문제'를 그래프로 도식화한 것으로, 이 경우는 한붓그리기가 불가능하다.

3.1. 꼭짓점의 차수

그래프에서 한 꼭짓점에 연결된 변의 개수이다. 단, 고리(한 변의 양 끝 꼭지점이 같을 때 그 변)는 2개의 변으로 생각한다.

기호로 Deg(a)로 표기한다.

그래프의 변의 개수가 k개일 때, 다음과 같은 정리가 성립한다.
Σ Deg(P) = 2k[1]
홀수점 (또는 홀수 결절점) (Deg(P) = 2k - 1(홀수))의 개수는 짝수개이다.

3.2. 꼭짓점 차수가 모두 짝수

파일:Euler_trail_01.png
이 경우에는 어떤 점에서 출발해도 다시 출발점으로 되돌아올 수 있다. 즉, 오일러 회로가 존재한다. 대표적인 그래프로 흔히 그리는 꼭짓점 5개짜리 별 그림이 있다.

3.3. 꼭짓점 차수가 2개만 홀수이고 나머지는 모두 짝수

파일:Euler_trail_02.png
차수가 홀수인 점이 A와 B라고 했을 때, A에서 출발하면 B로 도착하게 된다. 즉, 오일러 트레일은 존재하지만 오일러 회로는 존재하지 않는다. 위 그림에서 하단의 3에서 출발하면 반대편 3으로 도착하게 되는 것을 알 수 있다.

3.4. 그 외

홀수점이 2개를 넘을 때는 한붓그리기가 불가능하다. 홀수점이 홀수개인 경우는 존재할 수 없으므로, 4개 이상 부터는 한붓그리기가 불가능하다.

증명은 비교적 간단하다. 한붓그리기는 들르는 점에 상관없이 변을 모두 지났냐에 초점을 두기에, 하나의 단일 폐곡선으로 볼 수 있다. 이때 홀수점이 4곳 이상이라면 중간에 고립된 곡선이 생기므로 한붓 그리기가 불가능하다.

이해가 어렵다면 다음을 상상해 보자. 직접 그리면 더 좋다.
원 위에 점 A,B,C,D를 순서대로 잡자. 그리고 호 AB와 호 CD를 없애보자. 그러면 A, B, C, D 모두 홀수점이 된다.
이때 BC는 고립되었으므로 지나갈 수 없다. 따라서 한붓그리기는 불가능하다.

나아가 홀수점이 2k개인 그래프는 붓을 최소 k번 써서 그려야 한다. 즉, 맨 위의 그림은 홀수점이 4개이므로 붓을 최소 2번 써서 (1번은 떼서) 그려야 한다.

오일러 회로의 경우 다른 간선을 선택할 수 없는 경우가 아닌 한 bridge(지워진다면 그래프가 비연결이 되는 간선) 외의 간선을 선택하며 경로를 만들 경우(이 때 선택된 간선은 그래프에서 지우고, 인접한 간선들이 모두 지워진 정점도 지우면서 과정을 반복하면 된다.) 이것이 실제로 원래대로 돌아오는 경로라는 것이 보장되는데, 이를 fleury's algorithm이라고 한다. 다만 간선이 bridge인지 판단하는 것이 어려우므로 이 알고리즘은 이론적인 의미가 강한 알고리즘이다.

4. 고등학교 교육과정

2015년 기준 고등학교 3학년까지는 '행렬과 그래프' 단원에서 한붓그리기가 가능한 그래프에 대해 배운다. 다만 새 교육과정을 적용받는 고1, 고2부터는 행렬 단원 자체가 아예 빠져서 더 이상 한붓그리기에 대해 배우지 못한다.

5. 응용

FDM 3D 프린터를 사용하기 위한 슬라이서 프로그램도 한붓그리기 알고리즘을 적극적으로 사용한다. 최대한 적게 움직이면서 다른 선의 시작지점으로 이동하기 위한 리트랙션(되감기) 횟수를 최소화해서 출력 시간을 최적화함과 동시에 출력 품질을 올릴 수 있기 때문. 그래서 모델을 출력 명령어인 gcode로 변환하는 프로그램인 슬라이서들은 재료를 어느 정도 손해보더라도 강제로 한붓으로 잇는 옵션 또한 제공한다. SLA방식 3D프린터의 경우에도 레이저의 이동경로가 얼마나 최적화되냐에 따라 출력 속도가 정해진다.

6. 한붓그리기 게임

머리를 써야 하는 퍼즐이기 때문에 여러 게임에서도 한붓그리기를 사용한다.

7. 기타

  • 문제적 남자에서 ⊙ 모양으로 한붓그리기를 하기 도전과제가 있었는데, 해답은 종이를 살짝 접어서 그리는 것이었다. 물론 이 문제는 수학적으로 한붓그리기라 말할 수 없다.
  • 악필인 사람들 중에서는 띄어 쓰는 곳을 제외하고 필기구를 떼지 않고 오로지 필압으로만 의지해 아랍어처럼 거의 한 획으로 적는 사람들도 있다. 이를 본 사람들은 그런 사람들을 보고 "한붓그리기를 하느냐?"는 말을 하기도 한다.

[1] 모든 점의 차수의 합은 변의 개수의 2배이다.