수학과 사는 이야기

해밀토니안(Hamiltonian) 1857년 영국의 수학자 해밀톤은 아래와 같은 세계 일주 게임을 소개했다. 정십이면체의 꼭짓점 20개에 세계의 이름난 도시 이름을 붙이고 어느 한 도시를 출발하여 모서리를 따라 다른 도시를 모두 방문하고 출발한 도시로 돌아오시오. 이때 한 번 지나간 도시를 다시 지날 수는 없다. 이산수학 문제는 쉬워 보이지만 막상 풀어보면 쉽지 않은 것들이 많다. 먼저 그래프에서 모든 꼭짓점을 지나는 경로는 '해밀톤 경로(Hamiltonian path)'이고 출발점과 끝점이 같으면 '해밀톤 회로(Hamiltonian circuit)'이다. 해밀턴 회로를 가진 그래프를 '해밀토니안(Hamiltonian)'으로 부른다. 어떤 그래프가 '해밀토니안'인가를 단박에 알아내기는 쉽지 않다. 해밀톤..