해밀턴 경로와 순환 해설

점 다섯 개를 둥글게 찍고 각각을 양옆 이웃과 이어 보세요. 모든 점을 한 번씩 지나 한 바퀴 돌아 집으로 돌아올 수 있습니다. 이것이 해밀턴 순환입니다. 변을 몇 개 더하거나 빼면 문제는 놀랄 만큼 어려워집니다. 그래프에 그런 순환이 있는지는 어떤 컴퓨터도 아직 모든 그래프에 대해 빠르게 답하지 못하는 가장 잘 알려진 문제 가운데 하나입니다.

납작하게 편 정십이면체. 스무 꼭짓점에 자음이 적혀 있고, 그 모두를 지나는 해밀턴 순환이 밝은 선으로 그려져 있으며, 탐색이 되돌아간 자리에는 빨간 점선 변이 있다
납작하게 편 정십이면체. 스무 꼭짓점에 자음이 적혀 있고, 그 모두를 지나는 해밀턴 순환이 밝은 선으로 그려져 있으며, 탐색이 되돌아간 자리에는 빨간 점선 변이 있다

모든 꼭짓점을 한 번씩

그래프는 꼭짓점이라 부르는 점들의 모임이 변이라 부르는 선으로 이어진 것입니다. 해밀턴 경로는 변을 따라가며 모든 꼭짓점을 정확히 한 번씩 지나고, 해밀턴 순환은 거기에 더해 출발한 자리로 돌아오므로 변의 수가 꼭짓점의 수와 같습니다. 해밀턴 순환이 있는 그래프를 해밀턴 그래프라고 합니다. 제시된 길을 확인하기는 쉽습니다. 꼭짓점을 세고 한 걸음씩 살펴보면 됩니다. 어려운 쪽은 하나를 찾아내거나 하나도 없음을 보이는 일입니다. 꼭짓점을 방문할 수 있는 순서의 수가 n!처럼 늘어나, 꼭짓점 20개에서 벌써 2.4 × 10¹⁸이 되기 때문입니다.

해밀턴의 이코시안 게임

사원수를 발견한 아일랜드 수학자 윌리엄 로언 해밀턴은 1857년에 이코시안 게임을 만들었습니다. 판에는 평면에 납작하게 편 정십이면체가 그려져 있고 스무 꼭짓점에 자음이 적혀 있었으며, 주된 과제는 1부터 20까지 번호가 붙은 못을 꼭짓점에 꽂되 이웃한 번호끼리, 그리고 20과 1이 변으로 이어지게 하는 것이었습니다. 해밀턴은 권리를 25파운드에 런던 장난감 제조사 John Jaques and Son에 팔았고, 1859년에 출시되었지만 잘 팔리지 않았습니다. 이 퍼즐의 해는 출발점과 방향에 상관없이 순환을 한 번으로 세면 30가지입니다. 물음 자체는 새롭지 않았습니다. 토머스 커크먼은 1855년 왕립학회에 보낸 논문에서 어떤 다면체에 모든 꼭짓점을 지나는 순환이 있는지 물었고, 그런 순환이 없는 예를 하나 보였습니다.

나이트 투어

나이트 투어는 체스의 나이트를 움직여 모든 칸에 정확히 한 번씩 내려놓는 것입니다. 칸을 꼭짓점으로, 나이트의 수를 변으로 하는 그래프에서의 해밀턴 경로입니다. 닫힌 투어는 출발점에서 나이트 한 수 거리에서 끝나므로 해밀턴 순환입니다. 체스를 두는 사람들은 천 년도 더 전부터 이런 문제를 냈고, 오일러는 1759년 논문에서 이를 연구했습니다. 1823년 H. C. 폰 바른스도르프는 언제나 다음 수가 가장 적은 칸으로 가라고 제안했습니다. 이 단순한 규칙은 8 × 8 판의 투어를 대체로 되돌아가지 않고 끝냅니다. 나이트는 언제나 칸 색을 바꾸므로 닫힌 투어에는 밝은 칸과 어두운 칸이 같은 수만큼 필요하고, 그래서 칸 수가 홀수인 판은 제외됩니다. 앨런 슈웽크는 1991년에 어떤 직사각형 판에 닫힌 투어가 있는지 정확히 밝혔습니다. 정사각형 판 가운데는 한 변이 6 이상의 짝수인 판에 모두 있습니다. 보통의 체스판에는 닫힌 투어가 13,267,364,410,532가지 있으며, 브렌던 매케이가 1997년에 세었습니다.

해밀턴 순환이 없는 그래프

순환이 없음을 보이는 가장 빠른 증명은 세어 보는 논법입니다. 모든 변이 서로 다른 색을 잇도록 꼭짓점을 두 색으로 칠할 수 있다면, 순환은 색을 번갈아 밟으므로 각 색의 꼭짓점이 같은 수만큼 필요합니다. 5 × 5 격자는 한 색이 13개, 다른 색이 12개여서 해밀턴 순환이 없습니다. 없애면 그래프가 갈라지는 절단점은 두 번 지나야 하고, 차수가 1인 꼭짓점은 아예 지나갈 수 없습니다. 이런 논법을 모두 빠져나가는 그래프도 있습니다. 1898년 율리우스 피터슨이 발표한 피터슨 그래프는 차수가 3인 꼭짓점 10개를 가지며 해밀턴 순환이 없지만, 어느 꼭짓점이든 하나를 지우면 해밀턴 순환이 있는 그래프가 남습니다. 그런 성질을 가진 가장 작은 하이포해밀턴 그래프입니다. 1862년 이코시안 게임에 관해 글을 쓴 알렉산더 스튜어트 허셜의 이름을 딴 허셜 그래프는 꼭짓점 11개와 변 18개를 가지며, 사각형 면이 아홉 개인 다면체의 그래프입니다. 꼭짓점이 더 적은 다면체 가운데 해밀턴 순환이 없는 것은 없습니다. 1884년 피터 거스리 테이트는 각 꼭짓점에 모서리가 세 개씩 모이는 다면체에는 모두 해밀턴 순환이 있다고 추측했지만, W. T. 터트가 1946년에 꼭짓점 46개짜리 반례를 찾아냈습니다.

존재를 보장하는 조건

그래프에 변이 많으면 해밀턴 순환은 확실합니다. 게이브리얼 디랙은 1952년에 꼭짓점이 n ≥ 3개이고 모든 꼭짓점의 차수가 n/2 이상인 그래프에는 해밀턴 순환이 있다고 증명했고, 외위스테인 오레는 1960년에 조건을 약하게 만들었습니다. 이어져 있지 않은 두 꼭짓점의 차수 합이 언제나 n 이상이기만 하면 된다는 것입니다. 두 조건 모두 한 방향으로만 통합니다. 꼭짓점 100개짜리 단순한 고리는 어디서나 차수가 2로 50에 한참 못 미치지만, 그 자체가 해밀턴 순환입니다. 전체 그림은 이렇습니다. 충분조건이 있고 실패의 이유가 있으며, 그 사이에는 탐색만이 판정할 수 있는 넓은 그래프의 영역이 놓여 있습니다.

빠른 판정법이 알려져 있지 않은 이유

그래프에 해밀턴 순환이 있는지 판정하는 문제는 NP-완전이며, 1972년 리처드 카프가 꼽은 21개 문제 가운데 하나였습니다. 모든 그래프에 대해 이를 빠르게 푸는 방법이 있다면 다른 수천 가지 문제도 빠르게 풀리고 P 대 NP 문제도 결판날 것입니다. 모든 변을 한 번씩 쓰는 오일러 경로와의 대비가 뚜렷합니다. 오일러는 1736년에 홀수 차수 꼭짓점을 세면 그 물음이 곧바로 판정된다고 보였습니다. 해밀턴 순환을 위한 가장 좋은 정확한 방법들도 여전히 지수 시간이 걸립니다. 꼭짓점의 모든 부분집합을 훑는 동적 계획법은 1962년 리처드 벨먼과, 마이클 헬드 및 리처드 카프가 찾아낸 것으로 약 n² × 2ⁿ 단계가 들고, 안드레아스 비외르클룬드의 2010년 무작위 방법은 약 1.657ⁿ입니다. 실제로는 가지치기를 잘한 되추적이 꼭짓점 수십 개 규모의 그래프를 다루며, 가장 짧은 해밀턴 순환을 찾는 외판원 문제는 같은 물음에 가중치를 붙인 판입니다.

그레이 코드와 초입방체

0부터 7까지의 수를 3비트 부호로 적고 딱 한 비트만 다른 두 부호를 이어 보세요. 그러면 정육면체의 그래프가 됩니다. 그 안의 해밀턴 순환, 예를 들어 000, 001, 011, 010, 110, 111, 101, 100은 여덟 부호를 늘어놓되 각 부호가 바로 앞 부호와 한 비트만 다르게 합니다. 그런 목록이 그레이 코드이며, 1947년에 낸 특허에서 이를 설명한 벨 연구소의 프랭크 그레이의 이름을 땄습니다. 모든 초입방체에 하나씩 있습니다. 한 비트 짧은 부호들을 적고, 이어서 같은 목록을 거꾸로 적은 다음, 앞쪽 절반 앞에 0을, 뒤쪽 절반 앞에 1을 붙이면 됩니다. 회전 엔코더가 그레이 코드를 쓰는 것은 두 위치 사이에서 읽은 값이 한 단계를 넘어 틀리지 않게 하기 위해서입니다. 정육면체에는 해밀턴 순환이 6개, 4비트 초입방체에는 1,344개 있습니다.

직접 살펴보기

해밀턴 경로 탐색기를 열어 해밀턴의 퍼즐을 직접 풀어 보세요. 점선 고리가 다음에 갈 수 있는 곳을 보여 줍니다. 아니면 탐색으로 바꿔 되추적이 일하는 모습을 보세요. 경로가 자라고, 빨간 점선이 되돌아간 자리를 표시하며, 막대가 경로 길이별 노드 수를 셉니다. 막다른 길 검사와 연결성 검사, 바른스도르프 순서를 켜고 끄면서 각각 노드를 얼마나 쓰는지 비교하고, 작은 그래프의 순환을 모두 세어 보거나, 직접 그래프를 그려 어떤 빠른 판정이 들어맞는지 확인해 보세요.

자주 묻는 질문

오일러 회로가 있는 그래프는 해밀턴 그래프이기도 한가요? 반대는요?

둘 중 어느 쪽도 다른 쪽에서 따라 나오지 않습니다. 꼭짓점 하나를 함께 쓰는 삼각형 두 개인 나비넥타이는 모든 차수가 짝수라 오일러 회로가 있지만, 함께 쓰는 꼭짓점을 두 번 지나야 하므로 해밀턴 순환은 없습니다. 완전 그래프 K₄에는 해밀턴 순환이 있지만 네 꼭짓점의 차수가 모두 3이라 오일러 회로는 없습니다.

컴퓨터가 모든 순서를 그냥 다 시도하면 되지 않나요?

작은 그래프에서만 그렇습니다. 꼭짓점 n개의 순서는 n!가지이고 20개면 약 2.4 × 10¹⁸입니다. 되추적은 훨씬 낫습니다. 변만 따라가고 막히는 즉시 부분 경로를 버리기 때문입니다. 꼭짓점 20개짜리 정십이면체의 순환 30개를 모두 약 1,400단계에 찾아냅니다. 그래도 어떤 그래프에서는 부분 경로의 수가 여전히 지수적으로 늘고, 이를 모든 그래프에서 피하는 방법은 알려져 있지 않습니다.

해밀턴 경로 문제가 순환 문제보다 쉬운가요?

아닙니다. 둘 다 NP-완전입니다. 서로 바꿀 수 있습니다. 기존의 모든 꼭짓점과 이어진 새 꼭짓점을 하나 더하면, 원래 그래프에 해밀턴 경로가 있다는 것과 새 그래프에 해밀턴 순환이 있다는 것이 정확히 같아집니다. 반대 방향으로는, 어떤 꼭짓점의 복사본을 같은 이웃을 갖도록 더하고 그 꼭짓점과 복사본에 각각 새 끝 꼭짓점을 붙이면 순환 문제가 경로 문제가 됩니다.

5 × 5 판의 나이트 투어는 왜 모서리 색에서 시작해야 하나요?

칸 25개 가운데 13개가 모서리와 같은 색이고 12개가 다른 색이며, 나이트는 한 수마다 색을 바꿉니다. 칸 25개를 도는 투어는 색을 번갈아 밟으므로, 칸이 더 많은 색에서 시작해 그 색에서 끝납니다. 앱은 5 × 5 판의 열린 투어 1,728가지를 모두 찾아내며, 투어와 그 역순을 하나로 세면 864가지이고, 그 모두가 모서리 색 칸에서 시작해 그런 칸에서 끝납니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

해밀턴 경로 탐색기 열기