한붓 그리기

그래프의 한붓 그리기란, 그래프의 모든 간선을 정확히 한 번씩 통과하는 경로를 말한다.

우리는 아래 그래프에서, 한 정점에서 출발해서 한붓 그리기를 하고 출발한 정점으로 돌아오도록 하고 싶다.

하지만 안타깝게도 아래 그래프는 한붓 그리기를 할 수 없는 그래프로 알려져 있다.

대신, 이 그래프에 간선 3개를 적절히 추가로 그으면 한붓 그리기를 하고 출발한 정점으로 다시 돌아올 수 있다.

그래프에 추가 간선을 3개 그은 다음, 한붓 그리기를 하고 출발한 정점으로 돌아와 보자.

아래 [1번째 선 긋기], [2번째 선 긋기] 또는 [3번째 선 긋기] 버튼을 누른 다음 두 정점을 클릭하면 그래프에 추가 간선을 그을 수 있다. 세 개의 추가 간선을 그은 다음, [한붓 그리기 시작하기] 버튼을 누르면 한붓 그리기를 시작할 수 있다. 한붓 그리기를 시작할 정점을 클릭한 다음, 이후 방문할 정점을 순서대로 클릭하면 된다.

채점 방식

• 한붓 그리기를 하고 출발한 정점으로 돌아오는 데에 성공했으면 전체 점수의 100%를 받는다.