경로
살펴본 노드
해밀턴 순환
해밀턴 경로

모드

    목표

    해밀턴 경로와 순환에 대해 더 알아보기

    해밀턴 경로 탐색기

    1857년 윌리엄 로언 해밀턴은 퍼즐 하나를 만들었습니다. 정십이면체의 모서리를 따라 걸어 스무 개의 꼭짓점을 정확히 한 번씩 지나고 출발한 자리에서 끝내는 것입니다. 이런 길을 오늘날 해밀턴 순환이라고 부릅니다. 확인하기는 쉽지만 대개 찾기는 어렵습니다. 해밀턴의 정십이면체나 체스판, 직접 그린 그래프 위에서 한 번 따라 그려 보거나, 되추적 탐색이 순환을 쫓는 모습을 지켜보며 빠져든 막다른 길을 세어 보고, 몇 가지 간단한 검사가 탐색을 얼마나 줄이는지 확인해 보세요. 그래프와 목표를 고르세요. 출발점으로 되돌아오는 순환이거나 한 줄짜리 경로입니다. 따라 그리기: 꼭짓점을 눌러 시작하고 그다음에는 이웃을 하나씩 누릅니다. 점선 고리가 다음에 갈 수 있는 곳을 보여 줍니다. 마지막 꼭짓점을 누르거나 뒤로, 실행 취소를 누르면 한 걸음 돌아가고, 힌트는 아직 끝까지 갈 수 있는 다음 한 걸음을 알려 줍니다. 탐색: 실행이나 단계를 누르면 되추적 탐색이 돌아갑니다. 막힐 때까지 꼭짓점을 덧붙이다가 막히면 되돌아갑니다. 빨간 점선은 되돌아간 자리를 보여 주고, 막대는 경로 길이별 노드 수를 셉니다. 시작하기 전에 꼭짓점을 누르면 어디에서 시작할지 고를 수 있습니다. 체크 상자는 가지치기를 켜고 끄며, 비교는 같은 탐색을 가지치기 있을 때와 없을 때로 돌리고, 모두 세기는 작은 그래프의 순환이나 경로를 모두 셉니다. 편집: 눌러서 꼭짓점을 더하고, 두 꼭짓점을 누르면 잇거나 끊을 수 있으며, 끌어서 옮기고, 삭제는 선택한 꼭짓점을 없앱니다.

    작동 원리

    1. 그래프를 고르세요. 해밀턴의 정십이면체, 피터슨 그래프, 나이트 투어 같은 것이 있고, 편집에서 직접 그릴 수도 있습니다. 그리고 목표로 순환이나 경로를 고르세요.
    2. 따라 그리기에서는 꼭짓점을 눌러 시작한 뒤 이웃을 하나씩 누릅니다. 뒤로와 실행 취소는 한 걸음 돌아가고, 힌트는 아직 끝까지 갈 수 있는 다음 한 걸음을 보여 줍니다.
    3. 탐색에서는 실행이나 단계를 눌러 되추적이 길을 찾는 모습을 지켜보고, 가지치기를 켜고 끄며, 비교를 눌러 각 방식이 노드를 얼마나 쓰는지 살펴보세요.

    해밀턴과 오일러

    오일러 경로는 모든 변을 한 번씩 쓰고, 해밀턴 경로는 모든 꼭짓점을 한 번씩 지납니다. 비슷하게 들리지만 성질은 아주 다릅니다. 연결 그래프에 오일러 경로가 있는지는 오일러가 1736년에 보인 대로 홀수 차수 꼭짓점을 세면 판정됩니다. 그런 꼭짓점이 없거나 둘일 때 존재합니다. 해밀턴 경로에는 그런 규칙이 알려져 있지 않습니다. 그래프에 해밀턴 순환이 있는지 판정하는 문제는 NP-완전이며, 1972년 리처드 카프가 꼽은 21개 문제 가운데 하나입니다. 그러니 이 문제에 빠른 방법이 생긴다면 다른 수천 가지 어려운 문제도 빠르게 풀릴 것입니다. 대신 일부 그래프를 판정해 주는 조건들이 있습니다. 1952년 디랙 정리는 모든 꼭짓점의 차수가 n/2 이상이면 해밀턴 순환이 있다고 보장하고, 1960년 오레 정리는 이어져 있지 않은 두 꼭짓점의 차수 합이 언제나 n 이상이면 그렇다고 말합니다. 차수가 1인 꼭짓점, 절단점, 크기가 다른 두 색깔 모둠은 순환을 배제합니다.

    탐색이 작동하는 방식

    되추적은 꼭짓점을 하나씩 붙여 경로를 만들고, 막히면 마지막 한 걸음을 물린 뒤 다음 이웃을 시도합니다. 해밀턴 순환이 있다면 언제나 찾아내지만, 부분 경로의 수는 지수적으로 늘어날 수 있습니다. 해밀턴 순환이 없는 5 × 5 격자에서는 그냥 되추적이 확신하기까지 노드 153,745개를 살핍니다. 두 가지 검사가 가망 없는 경로를 일찍 끊습니다. 빈 이웃이 둘보다 적은 미방문 꼭짓점은 더 이상 순환에 들어갈 수 없고, 미방문 꼭짓점들이 따로 떨어진 조각으로 나뉘면 하나의 경로로는 그것들을 덮을 수 없습니다. 둘을 함께 쓰면 같은 증명이 노드 1,761개로 끝납니다. 1823년 바른스도르프 규칙은 이어지는 수가 가장 적은 이웃부터 시도해, 8 × 8 나이트 투어를 모서리에서 출발해 막다른 길 한 번 없이 64수 만에 찾아냅니다.

    자주 묻는 질문

    해밀턴 경로와 해밀턴 순환은 무엇이 다른가요?

    해밀턴 경로는 그래프의 모든 꼭짓점을 정확히 한 번씩 지납니다. 해밀턴 순환은 똑같이 한 다음 변 하나를 더 따라 출발한 자리로 돌아오므로, 어느 꼭짓점에서든 시작할 수 있습니다. 해밀턴 순환이 있는 그래프에는 해밀턴 경로도 있지만(순환의 변 하나를 빼면 됩니다) 그 반대는 성립하지 않습니다. 피터슨 그래프에는 해밀턴 경로가 있고 해밀턴 순환은 없습니다.

    정십이면체에 해밀턴 순환이 있나요?

    있습니다. 출발점과 방향에 상관없이 각 순환을 한 번으로 세면 30개입니다. 해밀턴은 1857년 이것을 이코시안 게임으로 만들었습니다. 납작하게 편 정십이면체의 스무 꼭짓점에 자음을 적은 판이었고, 권리는 런던 장난감 제조사 John Jaques and Son에 25파운드로 팔렸습니다. 앱의 모두 세기는 이 30개를 노드 약 1,400개로 찾아냅니다.

    5 × 5 격자에 해밀턴 순환이 없는 이유는 무엇인가요?

    점 25개를 체스판처럼 칠해 보세요. 13개가 한 색, 12개가 다른 색이 되고, 한 걸음마다 다른 색으로 넘어갑니다. 순환은 한 바퀴 내내 색을 번갈아 밟으므로 두 색이 같은 수여야 하는데, 13과 12로는 그럴 수 없습니다. 같은 논리가 점의 수가 홀수인 모든 격자에, 5 × 5나 7 × 7 판 위의 나이트에(나이트는 언제나 칸 색을 바꿉니다), 그리고 두 모둠이 꼭짓점 6개와 5개인 허셜 그래프에 적용됩니다. 해밀턴 경로는 여전히 가능합니다. 더 많은 색에서 시작해 그 색에서 끝납니다.

    바른스도르프 규칙은 어떻게 나이트 투어를 찾나요?

    H. C. 폰 바른스도르프는 1823년에 나이트를 언제나 다음 수가 가장 적은 칸으로 옮기자고 제안했습니다. 가장자리와 모서리 가까이에 있어 끊기기 쉬운 칸들이 그 덕분에 나이트가 아직 들어갈 수 있을 때 일찍 방문됩니다. 이 규칙은 경험 법칙일 뿐 보장은 아니고 동점은 어떻게든 가려야 하지만, 8 × 8 판에서는 대체로 되돌아가지 않고 투어를 끝냅니다. 이 앱처럼 되추적과 함께 쓰면 5 × 5 이상에서 열린 투어를, 6 × 6과 8 × 8 판에서 닫힌 투어를 찾아냅니다.

    완전 그래프에는 해밀턴 순환이 몇 개 있나요?

    n ≥ 3일 때 (n − 1)!/2개입니다. 출발 꼭짓점을 고정하면 나머지 n − 1개는 어떤 순서로든 올 수 있고, 각 순환은 방향마다 한 번씩 두 번 세어집니다. K₆에는 5!/2 = 60개, K₁₀에는 181,440개가 있습니다. 바로 이것이 외판원이 골라야 하는 순회 경로들이며, 모두 시도해 보는 일이 그토록 빨리 불가능해지는 까닭입니다.

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

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

    편집기로 이동