백과

1736년 독일의 쾨니히스베르크(Konigsberg) 다리 문제를 해결하기 위해 수학자이자 물리학자인 오일러가 처음으로 고안했다. 쾨니히스베르크의 다리 문제란 임의의 한 점에서 출발하여 일곱개의 다리를 단 한 번만 지나서 출발점으로 되돌아올 수 있는가 하는 문제로, 오일러는 모든 다리를 단 한 번만 거쳐서는 절대 출발한 지점으로 돌아올 수 없다고 결론지었다. 오일러는 이 쾨니히스베르크 다리 문제를 연필을 떼지 않고 선을 한 번씩만 그릴 수 있는가 하는 한붓그리기 문제로 바꿔서 생각한 것이다.

• 1
• 2

• 1쾨니히스베르크의 다리
• 2오일러의 그래프 표현

몇 개의 선과 그 끝점으로 이루어져 있고, 전체가 연결되어 있는 도형을 선형도형이라고 하는데, 선형도형의 점은 그곳에 나타나 있는 선의 개수가 짝수일 때를 짝수점, 홀수일 때를 홀수점이라 하며, 어떠한 점도 짝수점이거나 홀수점이다.

• 1
• 2

• 1선형도형의 홀수점과 짝수점 1
• 2선형도형의 홀수점과 짝수점 2

오일러는 한붓그리기를 할 수 있는 도형의 특징을 다음과 같이 정리했다.

• 1
• 2

• 1한붓그리기 가능

  홀수점이 2개이다.

• 2한붓그리기 불가능

  홀수점이 4개이다.

한붓그리기의 응용

동물원이나 놀이공원에 갈 때 중복된 길을 가지 않고 주어진 시간 안에 효율적으로 즐길 수 있는 방법을 찾다보면 그것이 한붓그리기의 법칙이다. 세일즈를 하거나 해외여행을 가려고 도시 간의 여행 계획을 짤 때도 최적 경로를 찾기 위해 한붓그리기를 하면 된다. 일상에서 단순한 한붓그리기 법칙을 쓰지 않는다면 엉뚱한 곳을 빙빙 돌다가 오거나 한 번 간 곳을 여러 번 지나게 될 수도 있다.

또한 모든 도로를 중복 없이 한번 씩만 지나도록 효율적으로 청소차 운행 계획, 우편배달부의 배달 경로를 짤 수도 있고, 전신주의 전기선을 효율적으로 배치할 때도 필요하다. 오일러 경로 외 회로는 점과 선으로 이루어진 도형을 연구하는 그래프 이론의 중요한 연구 주제로 교통공학, 컴퓨터 네트워크, 컴퓨터 칩의 설계 등의 다양한 분야에서 활용되고 있다.