상단여백
HOME 칼럼
[칼럼/ 고수학전문학원 고지윤 원장한붓그리기… 해밀턴 회로

“정십이면체의 20개의 꼭짓점에 적힌 한 도시에서 출발하여 모든 도시를 방문하고 처음으로 돌아오도록 하시오. 단, 한번 방문한 도시는 다시 방문하지 않는다.”

19세기 영국의 수학자 해밀턴은 위 문제를 다음과 같은 간단한 그래프로 표현하여 해결하였는데, 퀴즈 문제처럼 같은 길을 반복해서 지나지 않고 주어진 그래프 위의 모든 점을 한번씩 지나 출발점으로 돌아올 수 있는 길을 “해밀턴 회로(Hamiltonian cycle)”이라고 부른다.
회로라 하면 처음 지점으로 다시 돌아올 수 있는 길을 뜻하는데, 한붓그리기가 떠오를 것이다. 해밀턴 회로는 모든 꼭짓점을 지나야 하며, 같은 길을 반복하지 않는다면, 한붓그리기는  모든 길을 지나 처음 출발점으로 되돌아 오는 것을 뜻한다. 
“쾨니히스베르그시의 한 가운데는 프레골라 강이 흐르고 있고, 여기에는 가운데 섬들과 연결되어 있는 7개의 다리가 있다. 다음과 같이 놓여 있는 7개의 다리를 어느 다리나 한번씩만 차례로 모두 건널 수 있겠는가?”

오일러는 쾨니히스베르그 다리를 모두 지나 각 도시를 방문하는 방법을 고민하면서, 다음과 같은 그래프를 이용하여 1732년 절대 불가능함을 증명하였다.
가끔 학생들에게 색칠하기 문제에서 활용하기도 하는데, 강으로 분할되는 4개의 지역을 점으로 나타내고, 다리를 4점을 연결하는 선으로 생각할 때, 이 문제는 “한붓그리기”문제로 바뀌게 된다. 역시 위대한 오일러님!^^ 조금만 더~ 생각해보자. 한붓그리기가 모든 도형에서 가능할까? 
그렇지 않다. 한붓 그리기가 가능한 경우는 다음 두 가지 뿐이다. (한붓그리기 퍼즐 문제를 풀 때 꼭 기억해 두자)
1) 홀수점이 하나도 없는 경우에는 출발점과 도착점이 일치한다.
2) 홀수점이 두 개 있는 경우에는 출발점과 도착점이 다르다. (하나는 출발점과 도착점)
결론은 홀수점이 세 개 이상이면 한붓그리기는 절대 불가능하다. 쾨니히스베르그 다리를 그래프한 그림을 보면 꼭짓점에 연결된 선이 모두 홀수가 된다.(3, 3, 3, 5)
홀수점이 4개나 되므로 한붓그리기는 불가능하다. 한붓그리기의 원리를 알게 되었으니, 한번 실습해 보도록 하자.^^ 다음 그래프는 한붓 그리기가 가능할까?

다시, 해밀턴 이야기로 돌아오자, 해밀턴회로에 거리 개념까지 포함시킨 “영업사원문제 (travelling salesman problem)”가 있다. 영업사원이 한 도시를 출발하여 모든 도시를 통과한 다음 처음 출발했던 도시로 돌아오는 최단경로를 찾는 문제이다. 최소 경비로 영업사원이 모든 도시를 방문하는데, 이동하는 각 선에 교통비나 이동 거리와 같은 가중치를 두어서 해밀턴 회로를 찾는 문제이다. 이 문제는 아직도 효율적인 알고리즘을 찾지못한 난제로 남아있는데, 그래프에서 가능한 모든 회로를 찾아 비교하려면 통과하는 지점 수가 늘어날수록 계산하는데 어마어마한 시간과 노력이 들 것이다.
실제 그래프이론은 여러지역에 효율적으로 물건을 배송하거나, 전기 배선을 계획하거나, 최소의 경비로 관광지를 여행하는 코스를 찾을 때 등 다양한 영역에서 널리 활용되고 있는 유용한 이론이다.
그래프 이론은 수학적 이론에 그치지 않고 유전학, 사회학, 화학, 정보통신, 생태학, 교통문제 등 우리 생활 다양한 영역에서 그 위력을 발휘하고 있는 것! 아직도 해결되지 못한 수학적 난제들을 해결할 수 있는 사람이 바로 여러분이 아닐까? 행복한 상상을 해본다. 

편집국  sisanewsn@sisanewsn.co.kr

<저작권자 © 시사뉴스앤, 무단 전재 및 재배포 금지>

편집국의 다른기사 보기
icon인기기사
기사 댓글 0
전체보기
첫번째 댓글을 남겨주세요.
Back to Top