문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 한붓그리기 (문단 편집) === 그 외 === 홀수점이 2개를 넘을 때는 한붓그리기가 불가능하다. 홀수점이 홀수개인 경우는 존재할 수 없으므로, 4개 이상 부터는 한붓그리기가 불가능하다. 증명은 비교적 간단하다. 한붓그리기는 들르는 점에 상관없이 변을 모두 지났냐에 초점을 두기에, 하나의 단일 폐곡선으로 볼 수 있다. 이때 홀수점이 4곳 이상이라면 중간에 고립된 곡선이 생기므로 한붓 그리기가 불가능하다. 이해가 어렵다면 다음을 상상해 보자. 직접 그리면 더 좋다. 원 위에 점 A,B,C,D를 순서대로 잡자. 그리고 호 AB와 호 CD를 없애보자. 그러면 A, B, C, D 모두 홀수점이 된다. 이때 BC는 고립되었으므로 지나갈 수 없다. 따라서 한붓그리기는 불가능하다. 나아가 홀수점이 2k개인 그래프는 붓을 최소 k번 써서 그려야 한다. 즉, 맨 위의 그림은 홀수점이 4개이므로 붓을 최소 2번 써서 (1번은 떼서) 그려야 한다. 오일러 회로의 경우 다른 간선을 선택할 수 없는 경우가 아닌 한 bridge(지워진다면 그래프가 비연결이 되는 간선) 외의 간선을 선택하며 경로를 만들 경우[* 이 때 선택된 간선은 그래프에서 지우고, 인접한 간선들이 모두 지워진 정점도 지우면서 과정을 반복하면 된다.] 이것이 실제로 원래대로 돌아오는 경로라는 것이 보장되는데, 이를 fleury's algorithm이라고 한다. 다만 간선이 bridge인지 판단하는 것이 어려우므로 이 알고리즘은 이론적인 의미가 강한 알고리즘이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기