[include(틀:이산수학·수리논리학)] [목차] == 개요 == [[파일:external/upload.wikimedia.org/500px-K%C3%B6nigsberg_graph.svg.png]] 이 그림은 한붓그리기가 불가능하다.[* 한붓그리기가 불가능한 것으로 유명한 '[[쾨니히스베르크 다리 건너기 문제]]'를 그래프로 도식화한 것.] 한 번 지나간 선으로는 지나가지 않고 모든 선을 이어 그림을 완성하는 것. 붓을 종이에서 떼지 않고 한 번에 그린다고 해서 '한붓그리기'라는 이름이 붙었다. [[이산수학]]에서는 경로가 닫혀있느냐[* 출발점으로 다시 되돌아오면 닫힌 경로라고 한다.] 아니냐에 따라 '''오일러 트레일'''(Euler trail), 또는 '''오일러 회로'''(Euler circuit)이라고 부른다. 우체부[* 정확히 우체부인지는 불명.]가 쾨니히스베르크[* 지금은 [[러시아]]의 칼리닌그라드.]에 있는 [[쾨니히스베르크 다리 건너기 문제|7개의 다리를 단 한 번씩만 건너서 다시 출발점으로 되돌아올 수 있겠냐는 문제]]를 1736년에 [[레온하르트 오일러]]가 [[그런 거 없다]]라고 증명한 것을 한붓그리기의 이론적 출발점으로 보고 있다. 비슷한 그래프 이론 문제로는 모든 '''변'''을 한 번만 지나야 하는 한붓 그리기 문제와는 반대로 모든 '''꼭짓점'''을 모두 한 번만 방문해야 하는 [[해밀턴 경로]] 문제도 있다. == 한붓그리기가 가능하려면? == [[2015년]] 기준 고등학교 3학년까지는 '행렬과 그래프' 단원에서 한붓그리기가 가능한 그래프에 대해 배운다. 다만 새 교육과정을 적용받는 고1, 고2부터는 행렬 단원 자체가 아예 빠져서 더 이상 한붓그리기에 대해 배우지 못한다. === 꼭짓점의 차수 === [[그래프]]에서 한 꼭지점에 연결된 변의 개수이다. 단, 고리[* 한 변의 양 끝 꼭지점이 같을 때 그 변을 고리라고 한다.]는 2개의 변으로 생각한다. 기호로 Deg(a)로 표기한다. 그래프의 변의 개수가 k개일 때, 다음과 같은 정리가 성립한다. > Σ Deg(P) = 2k[* 모든 점의 차수의 합은 변의 개수의 2배이다.] > 홀수점 (또는 홀수 결절점) (Deg(P) = 2k - 1(홀수))의 개수는 짝수개이다. === 꼭짓점 차수가 모두 짝수 === [[파일:Euler_trail_01.png]] 이 경우에는 어떤 점에서 출발해도 다시 출발점으로 되돌아올 수 있다. 즉, 오일러 ''회로''가 존재한다. 대표적인 그래프로 흔히 그리는 꼭짓점 5개짜리 [[별]] 그림이 있다. === 꼭짓점 차수가 2개만 홀수이고 나머지는 모두 짝수 === [[파일:Euler_trail_02.png]] 차수가 홀수인 점이 A와 B라고 했을 때, A에서 출발하면 B로 도착하게 된다. 즉, 오일러 ''트레일''은 존재하지만 오일러 ''회로''는 존재하지 않는다. 위 그림에서 하단의 3에서 출발하면 반대편 3으로 도착하게 되는 것을 알 수 있다. === 그 외 === 홀수점이 2개를 넘을 때는 한붓그리기가 불가능하다. 증명은 비교적 간단하다. 한붓그리기는 들르는 점에 상관없이 변을 모두 지났냐에 초점을 두기에, 하나의 단일 폐곡선으로 볼 수 있다. 이때 홀수점이 4곳 이상이라면 중간에 고립된 곡선이 생기므로 한붓 그리기가 불가능하다. 이해가 어렵다면 다음을 상상해 보자. 직접 그리면 더 좋다. 원 위에 점 A,B,C,D를 순서대로 잡자. 그리고 호 AB와 호 CD를 없애보자. 그러면 A, B, C, D 모두 홀수점이 된다. 이때 BC는 고립되었으므로 지나갈 수 없다. 따라서 한붓그리기는 불가능하다. == 게임 == 머리를 써야 하는 퍼즐이기 때문에 여러 게임에서도 한붓그리기를 사용한다. === 한붓그리기 게임목록 === * 게임 자체가 한붓그리기인 게임들 * [[https://apps.apple.com/kr/app/%ED%95%9C%EB%B6%93%EA%B7%B8%EB%A6%AC%EA%B8%B0/id494856551|한붓그리기]] - 게임 제목 자체가 '''한붓그리기'''이다. * Juice Cubes * [[디스코판다]] * 베스트핀즈 * [[포코팡]] * [[http://express.5minlab.com/ko/|Express Thru]] == 기타 == * 장난으로 ⊙ 모양으로 한붓그리기를 하기 도전과제가 있는데 해답은 종이를 살짝 접어서 그리는 것이다. [각주] [[분류:이산수학]][[분류:조합]]