수학

한붓그리기 이해하기

콘파냐 2017. 3. 30. 11:13
반응형

어떤 도형을 그릴 때 선을 떼지않고 한번에 그릴 수 있는 도형과 한번에 절대 못그리는 도형은 어떤 차이가 있을까? 오일러의 한붓그리기는 이런 차이에 대한 공식이다. 우선 한붓그리기에 있어서 점과 선(변)에 대한 정의를 명확히 할 필요가 있다.

▲ 위와 같은 모양은 선(변)의 개수는 4, 점의 개수는 4개가 된다.

그렇다면 다음 도형은 어떤가?

중간에 X의 선이 생겼고 그 교점이 추가되었다.

▲ 선은 점과 점 사이에 있어야한다. 비록 직선이더라도 선위에 점이 있을 수는 없다. 따라서 이 도형의 선의 개수는 8, 점의 개수는 5가된다. 


그러면 이번에는 위 도형이 한붓그리기가 가능한지 실험해보자.

아무리 그려도 한붓그리기가 안될 것이다. 그렇다면 다음 도형은 어떤가.

아주 쉽게 한붓그리기가 가능할 것이다.

하지만 도형이 복잡해 질 경우에는 모든 경우의 수를 그려서 한붓그리기 가능여부를 따지기는 힘들 수 있다. 따라서 한붓그리기가 가능한 경우를 일반화시키면 쉽게 한붓그리기 가능여부를 따질 수 있다.


도형의 각 점에서 연결된 선(변)의 개수를 적어보자

한붓그리기가 가능한지 따질 때는 각 점에서 연결된 선(변)의 개수가 홀수인 경우가 몇개인지 파악해야 한다. 오른편에 그림처럼 연결된 선의 개수가 홀수(3)인 경우가 2개인 경우는 한붓그리기가 가능하다.  왼편은 4개이므로 불가능하다. 


연결된 선(변)의 개수가 홀수인 점의 개수가 0 또는 2개인 경우에만 한붓그리기가 가능하다.


그렇다면 다음 왼편의 도형을 한붓그리기가 가능한 형태로 바꿀 수도 있다.

한붓그리기의 원리


한붓그리기를 하면 점을 기준으로 들어오는 선과 나가는 선이 있다. 다음과 같이 점에 연결된 선(변)이 짝수인 경우는

들어오는 선과 나가는 선의 개수가 동일하다. 

만약 이 점이 한붓그리기의 시작점이라면 나가는 선이 먼저 그려지게 된다. 그리고 들어오는선, 나가는선, 그리고 들어오는 선 순서대로 그려져야한다. 결국 이 점은 한붓그리기의 시작점이자 마지막 점이 되어야한다.


그러면 이번에는 점에 연결된 선(변)의 개수가 홀수인 경우를 살펴보자.


연결된 선이 홀수인 경우는 한붓그리기의 시작점 또는 마무리 점으로 쓰일 수 있다. 시작점으로 쓰인 경우는 나가는 선, 들어오는 선, 나가는 선 순서대로 한붓그리기가 가능하다. 보면 알겠지만 선이 홀수개이므로 시작점으로 쓰인 경우는 마무리점이 될 수 없다. 따라서 어디엔가 마무리 점이 있어야 한다.

마무리점의 경우는 들어오는선, 나가는선, 들어오는선의 순서대로 한붓그리기가 그려진다. 들어오는 선을 끝으로 더 이상 나가는 선이 없으므로 이 점은 반드시 한붓그리기의 마무리 점이 되어야한다.

따라서 더 이상의 점에 연결된 선의 개수가 홀수인 점은 없어야 한다.


예제) 다음 도형이 한붓그리기가 가능한지 알아보자.

위 그림은 케니히스베르크라는 도시의 7개의 다리를 간략화한 그림이다. 전기가 없던 시대에는 다리의 가로등을 일일이 불을 붙이고 꺼야했다. 매일 반복적인 작업이므로 가능한 번거롭지 않게 각 다리들을 단 한번만 건너서 작업을 할 수 있는 방법이 없을까 모색했지만, 아무도 풀지 못했다. 그러던 중 오일러는 각 다리를 단 한번만 건너서 작업을 마무리할 수 없다는 것을 알아내었다.

반응형