한붓그리기에서 홀수점 4개 이상이면 안되는 원리

Question

레이튼 교수 플레이하다가 한붓그리기 문제가 나와 질문드립니다.

간단한 인터넷 서칭으로는 결과만 알려주고, 결과에 대한 과정은 알려주질 않네요.

한붓그리기에서 홀수점이 0개거나 2개일 때 가능하다는건 알겠습니다. (출발점=도착점이 같다면, 홀수점이 존재안함. 출발점과 도착점이 다르다면, 홀수점 두개로 짝수이룸 때문에 홀수점이 홀수면 남는 선이 생겨서 불가능)

그런데 4개 이상의 짝수가 불가능한 이유를 도통 모르겠습니다.

수학 다 잊어먹은 아재도 이해할수 있을만큼 쉽게 설명해주실 분 계신가요?

Answer 1

안녕하세요. 전기기사 취득 후 현업에서 일하고 있는 4년차 전기 엔지니어 입니다.

한붓그리기의 원리는 그래프 이론에서 다루는데, 오일러 경로라는 개념이 중요합니다. 오일러 경로는 그래프상 모든 간선을 한 번씩만 지나가는 경로를 말합니다. 이러한 경로가 존재하려면 전체 그래프에서 홀수 차수의 꼭지점이 0 또는 2개여야 합니다. 홀수 차수의 꼭지점이 4개 이상이면 어느 한 지점에서 출발하더라도 모든 간선을 한 번씩 지나가는데 실패하게 됩니다. 그렇기 때문에 한붓그리기를 하기 위해서는 그래프의 구조와 홀수 차수의 개수를 잘 이해해야 합니다. 제 답변이 도움이 되셨길 바랍니다.

Answer 2

안녕하세요. 강세훈 전문가입니다.

한붓그리기에서 홀수점이 4개 이상일 때 불가능한 이유는, 각 점에서 출발하거나 도달할 때마다 선을 그어야 하기 때문입니다. 각 점은 짝수번의 선을 그어야 완전히 연결될 수 있습니다. 하지만 4개 이상의 홀수점이 있으면 연결할 수 있는 선의 수가 모자라서, 반드시 남는 선이 생깁니다. 즉, 홀수점이 4개 이상이면, 어떤 점에서는 선이 1번만 연결되고 다른 점에서는 3번 이상 연결되어 불완전한 경로가 만들어지므로 한붓그리기는 불가능해집니다.

Answer 3

안녕하세요. 김재훈 전문가입니다.

한붓그리기는 모든 선을 한 번씩만 지나야 하는데 각 점에서 지나간 만큼 다시 돌아와야 합니다 홀수 차수를 가진 점이 2개면 출발점과 도착점이 될 수 있지만, 4개 이상이면 서로 짝을 맞출 수 없어 선이 남게 됩니다. 즉, 홀수 차수가 4개 이상이면 일부 점에서 출발한 선이 돌아오지 못해 한붓그리기가 불가능합니다.

Answer 4

안녕하세요. 조일현 전문가입니다.

한 점에 연결된 선의 개수가 짝수면 짝수점, 홀수면 홀수점 입니다.

한붓그리기가 가능한 조건은 짝수 점만 있는 경우 또는 홀수점이 2개 인경우 입니다.

홀수점이 2개일 때는 하나는 시작점, 다른 하는 끝점이 되어야 합니다.

홀수점 4개 이상일 때 불가능한 이유는 홀수점은 시작점이나 끝점으로 사용될수 있습니다.

홀수점이 4개 이상이면 시작점과 끝점으로 사용할 수 있는 홀수점이 충분하지 않습니다.

홀수점이 4개 이상일 때 모든 선을 한번씩만 지나며 그릴 수 없게 됩니다.

이는 남는 선이 생기기 때문입니다.