|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
한 번 지나간 선으로는 지나가지 않고 모든 선을 이어 그림을 완성하는 것. 붓을 종이에서 떼지 않고 한 번에 그린다고 해서 '한붓그리기'라는 이름이 붙었다.이산수학에서는 오일러 경로(Euler trail), 또는 경로가 닫힌 경우[1] 특히 오일러 회로(Euler circuit)이라고 부른다.
우체부[2]가 쾨니히스베르크[3]에 있는 7개의 다리를 단 한 번씩만 건너서 다시 출발점으로 되돌아올 수 있겠냐는 문제를 1736년에 레온하르트 오일러가 불가능하다고 증명한 것을 한붓그리기의 이론적 출발점으로 보고 있다.
비슷한 그래프 이론 문제로는 모든 변을 한 번만 지나야 하는 한붓 그리기 문제와는 반대로 모든 꼭짓점을 모두 한 번만 방문해야 하는 해밀턴 경로 문제도 있다.
2. 한붓그리기가 가능하려면?
2015년 기준 고등학교 3학년까지는 '행렬과 그래프' 단원에서 한붓그리기가 가능한 그래프에 대해 배운다. 다만 새 교육과정을 적용받는 고1, 고2부터는 행렬 단원 자체가 아예 빠져서 더 이상 한붓그리기에 대해 배우지 못한다.이 그림은 한붓그리기가 불가능하다.[4]
2.1. 꼭짓점의 차수
그래프에서 한 꼭짓점에 연결된 변의 개수이다. 단, 고리[5]는 2개의 변으로 생각한다.기호로 Deg(a)로 표기한다.
그래프의 변의 개수가 k개일 때, 다음과 같은 정리가 성립한다.
Σ Deg(P) = 2k[6]
홀수점 (또는 홀수 결절점) (Deg(P) = 2k - 1(홀수))의 개수는 짝수개이다.
2.2. 꼭짓점 차수가 모두 짝수
이 경우에는 어떤 점에서 출발해도 다시 출발점으로 되돌아올 수 있다. 즉, 오일러 회로가 존재한다. 대표적인 그래프로 흔히 그리는 꼭짓점 5개짜리 별 그림이 있다.
2.3. 꼭짓점 차수가 2개만 홀수이고 나머지는 모두 짝수
차수가 홀수인 점이 A와 B라고 했을 때, A에서 출발하면 B로 도착하게 된다. 즉, 오일러 트레일은 존재하지만 오일러 회로는 존재하지 않는다. 위 그림에서 하단의 3에서 출발하면 반대편 3으로 도착하게 되는 것을 알 수 있다.
2.4. 그 외
홀수점이 2개를 넘을 때는 한붓그리기가 불가능하다. 홀수점이 홀수개인 경우는 존재할 수 없으므로, 4개 이상 부터는 한붓그리기가 불가능하다.증명은 비교적 간단하다. 한붓그리기는 들르는 점에 상관없이 변을 모두 지났냐에 초점을 두기에, 하나의 단일 폐곡선으로 볼 수 있다. 이때 홀수점이 4곳 이상이라면 중간에 고립된 곡선이 생기므로 한붓 그리기가 불가능하다.
이해가 어렵다면 다음을 상상해 보자. 직접 그리면 더 좋다.
원 위에 점 A,B,C,D를 순서대로 잡자. 그리고 호 AB와 호 CD를 없애보자. 그러면 A, B, C, D 모두 홀수점이 된다.
이때 BC는 고립되었으므로 지나갈 수 없다. 따라서 한붓그리기는 불가능하다.
나아가 홀수점이 2k개인 그래프는 붓을 최소 k번 써서 그려야 한다. 즉, 맨 위의 그림은 홀수점이 4개이므로 붓을 최소 2번 써서 (1번은 떼서) 그려야 한다.
오일러 회로의 경우 다른 간선을 선택할 수 없는 경우가 아닌 한 bridge(지워진다면 그래프가 비연결이 되는 간선) 외의 간선을 선택하며 경로를 만들 경우[7] 이것이 실제로 원래대로 돌아오는 경로라는 것이 보장되는데, 이를 fleury's algorithm이라고 한다. 다만 간선이 bridge인지 판단하는 것이 어려우므로 이 알고리즘은 이론적인 의미가 강한 알고리즘이다.
3. 게임
머리를 써야 하는 퍼즐이기 때문에 여러 게임에서도 한붓그리기를 사용한다.3.1. 한붓그리기 게임목록
- 게임 자체가 한붓그리기인 게임들
- 한붓그리기 - 게임 제목 자체가 한붓그리기이다.
- Juice Cubes
- 디스코판다
- 베스트핀즈
- 포코팡
- Hell girls
- Express Thru
4. 기타
- 문제적 남자에서 ⊙ 모양으로 한붓그리기를 하기 도전과제가 있었는데, 해답은 종이를 살짝 접어서 그리는 것이었다. 물론 이 문제는 수학적으로 한붓그리기라 말할 수 없다.
- FDM 3D 프린터를 사용하기 위한 슬라이서 프로그램도 한붓그리기 알고리즘을 적극적으로 사용한다. 최대한 적게 움직이면서 다른 선의 시작지점으로 이동하기 위한 리트랙션(되감기) 횟수를 최소화해서 출력 시간을 최적화함과 동시에 출력 품질을 올릴 수 있기 때문. 그래서 모델을 출력 명령어인 gcode로 변환하는 프로그램인 슬라이서들은 재료를 어느정도 손해보더라도 강제로 한붓으로 잇는 옵션 또한 제공한다. SLA방식 3D프린터의 경우에도 레이저의 이동경로가 얼마나 최적화되냐에 따라 출력 속도가 정해진다.
[1]
출발점으로 다시 되돌아오면 닫힌 경로라고 한다.
[2]
정확히 우체부인지는 불명.
[3]
지금은
러시아의
칼리닌그라드.
[4]
한붓그리기가 불가능한 것으로 유명한 '
쾨니히스베르크 다리 건너기 문제'를 그래프로 도식화한 것.
[5]
한 변의 양 끝 꼭지점이 같을 때 그 변을 고리라고 한다.
[6]
모든 점의 차수의 합은 변의 개수의 2배이다.
[7]
이 때 선택된 간선은 그래프에서 지우고, 인접한 간선들이 모두 지워진 정점도 지우면서 과정을 반복하면 된다.