정보올림피아드 초등 - 지역예선] 2009년도 15번문제

 

15.펜을 떼지 않고 도형을 그리는데 한 번 지나간 선을 다시 지나지 않고 모든 선을 지나도록 그릴 수 있다면 그 도형은 한붓그리기가 가능하다고 한다. 또, 모든 정점(vertex)이 다른 정점과 연결되어 있는 그래프를 완전그래프라고 하고, 정점의 개수가 n개인 완전그래프를 K 이라고 표시한다. 예를 들어, 다음 그래프는 K 를 나타낸다. 정점의 개수가 6인 완전그래프 K 에서 최소 몇 개의 선분을 빼내야 한붓그리기가 가능한가? 단, 시작점과 끝점이 같아야 한다.     ①0 ②1 ③2 ④3 ⑤4

문제 풀이) 한붓그리기가 가능한 경우는 한 정점에 연결되어 있는 선의 갯수가 모두 짝수이거나 홀수가 두개인 경우만 가능 한 것을 파악한다.

또한 시작한 점으로 되돌아 오는 경우는 모든 경우가 짝수인 경우에만 가능하다.

따라서 정점의 갯수가 6개인 도형을 그려 보면 다음과 같다.

 

여기서 정점의 선분 갯수가 모두 홀수 이므로 여기서 가장 최소의 선분을 삭제하여 모두 짝수로 만들면 된다.

따라서 아래 그림의 빨간 선을 제거 하면 모든 정점이 짝수로 만들어 진다.

 

따라서 최소 3개의 선 을 삭제 하면 처음 시작한 점이 끝점으로 만나는 한붓 그리기가 가능해 진다.

정답) 4번