자료 구조 시간에 배운 그래프중에서 오일러 회로와 해밀턴 회로가 헷갈려서 정리를 해 보았습니다.
사실 고등학생인 사촌동생이 수열과 관련지어서 그래프 문제를 질문했는데 헷갈려서 부끄러워 책좀 찾아 봤습니다.

[출처 : 천재교육 이산 수학 자습서 ] - 혹시 문제가 된다면 삭제 하도록 하겠습니다.

오일러 회로와 해밀턴 회로를 쉽게 이해 하기 위해서 신문 배달원과, 신문 배송 담당자이야기만 기억 하면 되겠습니다.

[신문 배달원이 처한 문제]
신문 배달을 시작한 철이는 며칠 동안 신문을 돌리다 보니 지나갔던 길을 또 지나가는 경우가 있는 것을 알게 되었다.
다음 그림은 배달 지역의 지도인데 모든 깅을 반드시 지나가야만 할때, 철이는 지나갔던 길을 다시 지나가지 않고 신문 배달을 잘 마칠 수 있을까?

[신문 배송 담당자]
철이가 신문 배달 하는 길을 놓고 고민하는 모습을 본 신문 배송 담당자는 철이에게 다음과 같은 말을 하였다.
"나도 새벽에 신문사에서 신문을 받아 각 지역 지국으로 배송하여야 하는데 어떻게 하면 좋을까?"
철이가 생각해보니 신문 배송 담장자의 문제는 철이의 경우와 조금 다른 것 같았다. 
왜냐하면 철이의 경우는 지나갔던 길만 지나지 않으면 되는데 신문 배송 담장자의 경우는 한 번 들린 지국에는 다시 들릴 필요가 없기 때문이다. 
이 문제를 해결하기 위해서 모든 꼭지점들을 오직 한 번만 지나면서 출발점으로 돌아오는 방법을 찾는 것이다.
신고
by danguria 2010.04.30 19:48