한붓그리기

 

한붓그리기란? 붓을 한 번도 종이 위에서 떼지 않고 같은 곳을 두 번 지나지 않으면서 어떤 도형을 그릴 수 있느냐 하는 문제로, L.오일러는 '한 점으로부터 짝수 개의 선이 나와 있는 것을 우점(偶點), 홀수 개의 선이 나와 있는 것을 기점(奇點)이라 하면, 우점만으로 되어 있는 도형이나, 기점이 2개인 도형으로서 그 한쪽을 출발점, 나머지 하나를 종점으로 하는 경우에만 한붓그리기는 가능하다'는 한붓그리기의 '오일러의 정리'를 발표했다.

한붓 그리기 공식은

'한 점으로부터 짝수 개의 선이 나와 있는 것을 우점(偶點), 홀수 개의 선이 나와 있는 것을 기점(奇點)이라 하면 우점만으로 되어 있는 도형이나, 기점이 2개인 도형으로서 그 한쪽을 출발점, 나머지 하나를 종점으로 하는 경우에만 한붓그리기는 가능하다.

 

종종 정보올림피아드 문제에서 한붓그리기가 가능 하도록 선을 그리거나 빼는 형태의 문제가 출제 됨.

출발점과 도착점이 같기 위해서는 한 점으로 부터 나와 있는 선이 모두 짝수개여야 하며 출발점과 도착점이 같지 않은 경우에는 한 점으로 부터 나와 있는 선이 홀수개인 점이 2개여야 한다.