2013년 12월 9일 월요일

영재교육원 수학특강 그래프 이론 - 해밀턴 경로

생활에서 일어나는 여러 가지 문제를 보다 과학적이고 체계적으로 해결하기 위해 필요한 그래프 이론을 기출문제를 중심으로 살펴보고 있다.

 해밀턴 경로
모든 점을 한 번씩만 지날 수 있는 길을 ‘해밀턴 길’, 모든 점을 돌아 다시 출발점으로 되돌아 올 수 있는 길을 ‘해밀턴 순환길’이라고 한다.

오일러 경로와 마찬가지로 주어진 상황을 점과 선으로 간단하게 나타낸 다음 모든 점을 한 번씩만 지나는 길을 완성하면 된다. 다만 해밀턴 경로 문제는 아직 일반화 된 이론은 없다. 따라서 다음과 같이 가능한 모든 경우를 생각해야한다.





 입체도형의 해밀턴 경로
입체도형에서 모든 꼭지점을 한 번씩 지나 출발점으로 돌아오는 해밀턴 순환길을 그려보자.
모서리를 따라 직접 입체도형에 그리는 방법과 모서리를 조금 늘리고, 꼭지점의 위치를 바꿔서 그리는 방법이 있다. 복잡한 도형일수록 후자의 경우로 도형을 변형시켜 경로를 찾는 것이 수월하겠다.






 해밀턴 경로를 이용한 문제
∙ 회사에서 출발해 그림과 같이 5개의 집을 모두 한 번씩 들러 물건을 배달하고 다시 회사로 돌아오는 배달차가 있습니다. 길 위에 수가 그 길을 지나는데 지불하는 통행료라고 할 때, 돈이 가장 적게 드는 경로를 찾아 그려 보시오.




① 그림을 점과 선으로 간단히 나타낸다.




② 가능한 해밀턴 순환길을 모두 찾아 각각의 경우 비용을 계산하여 돈이 가장 적게 드는 경로를 찾는다.
ⅰ) O-A-E-C-B-D-O (O-D-B-C-E-A-O) 700+300+200+300+400+400=2300(원)
ⅱ) O-A-C-E-D-B-O (O-B-D-E-C-A-O)
: 700+300+200+500+400+600=2700(원)
ⅲ) O-D-E-A-C-B-O (O-B-C-A-E-D-O)
: 400+500+300+300+300+600=2400(원)
따라서, O-A-E-C-B-D-O(O-D-B-C-E-A-O)가 2300원으로 돈이 가장 적게 드는 경로이다.

이렇게 최소 비용이 드는 최적의 경로를 찾기 위해서는 가능한 모든 경로를 찾아 그 값들을 비교해야한다.

 기출문제 풀이
∙ 보기의 도형 중 오일러 경로가 없으면서 해밀턴 경로가 있는 도형을 찾아 오일러 경로가 있는 도형이 되도록 최소 개수의 선을 그으시오.




한 점에서 만나는 선의 개수가 모두 짝수이거나 2개가 홀수인 경우 오일러 경로가 있는 도형이 된다. 따라서 도형 1, 2, 3은 홀수점의 개수가 4개, 6개, 4개이므로 오일러 경로를 그릴 수 없다. 도형 1, 2, 3은 모두 다음과 같은 해밀턴 경로를 그릴 수 있다.





오일러 경로가 없으면서 해밀턴 경로가 있는 도형 1, 2, 3을 오일러 경로가 있도록 최소 개수의 선을 그어보자. 도형 1과 3은 홀수 점이 4개이므로 선을 하나만 그으면 2개의 홀수점이 짝수점으로 변하고, 짝수점이 6개인 도형 2는 홀수점 4개를 짝수점으로 만들기 위해 2개의 선을 그어야 한다. 이 때 홀수점 중에서 2개를 골라 선으로 연결하는 방법은 여러 가지가 있을 수 있다.





∙ 정문에서 출발하여 동물들을 모두 관람하고 되돌아오는 가장 빠른 경로와 그 때의 거리, 걸리는 시간을 구하시오.





① 그림을 점과 선으로 간단하게 표현한다.
② 정문에서 출발하여 모든 점을 한 번씩 지나 다시 정문으로 돌아와야 하므로 모든 경우를 따져서 가장 짧은 해밀턴 순환길을 만들어야한다.
③ 같은 길을 한 번 더 가지 않는다는 가정에서 각각의 점에 들어오고 나가는 선 2개를 남기고 필요 없는 선을 지우면 어떨까.

가장 먼 길 400m, 350m를 먼저 지운다.(빨간 X) 최소한 한 개의 점과 이어진 길이 2개가 되도록 남겨두고(빨간 ○) 지운다.




④ 한 점에서 이어진 선(빨간 ○)이 2개가 되면 나머지 선은 모두 지우고(파란 X), 지울 수 없는 선은 남겨둔다.(녹색 ○) 지금까지 과정을 간단하게 나타내면 다음과 같다.




정문(O)를 출발해서 어느 방향으로 돌아도 출발점으로 돌아오는 가장 짧은 길이 완성된다.
1) 가장 짧은 이동경로는 방향에 상관없이
정문-원숭이-기린-펭귄-곰-호랑이-사자-코끼 리-정문

2) 가장 짧은 이동거리는
150+200+300+200+200+300+200+200=1750(m)

3) 따라서, 가장 짧은 시간은
17분30초(100m를 걷는데 1분)+70분(각각의 동물을 관람하는데 10분) = 87분30초이다.
∙ 8개의 방과 인접한 방들과 통하는 문을 모두 한 번씩만 통과 할 수 있는지 설명하시오.
그림과 같이 문을 선으로 방을 선분으로 나타내면 홀수점이 4개인 모든 선을 한번씩 지나는 오일러 경로를 그릴 수 없는 상태가 된다. 따라서 모든 문과 방을 한 번씩만 통과할 수 없다.








경향신문

댓글 없음:

댓글 쓰기