해밀턴 경로 검사기 (Hamiltonian Path Checker)

해밀턴 경로 검사기 (Hamiltonian Path Checker) 정보

해밀턴 경로 검사기는 그래프가 모든 정점을 정확히 한 번씩 방문하는 시퀀스인 해밀턴 경로, 또는 시작 정점으로 다시 돌아오는 해밀턴 회로를 포함하는지 여부를 결정합니다. 이 도구는 빠른 구조적 사전 점검(연결성, 차수 전제 조건, Dirac의 정리, Ore의 정리)과 Warnsdorff 휴리스틱으로 조정된 백트래킹 탐색을 결합하며, 증거 경로를 단계별 애니메이션으로 시각화합니다.

해밀턴 경로란 무엇인가요?

n개의 정점을 가진 그래프 G = (V, E)가 주어졌을 때, 해밀턴 경로는 인접한 각 쌍 (v_i, v_i+1)이 G의 간선이며 모든 정점이 정확히 한 번씩 나타나는 정점들의 순서 시퀀스 v₁, v₂, …, v_n를 말합니다. 추가적으로 (v_n, v₁)이 간선인 경우, 이 시퀀스는 해밀턴 회로가 됩니다.

이 문제는 1857년 정십이면체의 모든 정점을 정확히 한 번씩 방문하는 회로를 찾는 퍼즐인 이코시안 게임(Icosian game)을 발명한 William Rowan Hamilton의 이름을 따서 명명되었습니다.

어려운 이유: NP-완전성

해밀턴 경로 결정 문제와 해밀턴 회로 결정 문제 모두 NP-완전(Karp, 1972)입니다. P = NP가 아닌 한, 모든 사례를 다항 시간 내에 해결하는 알고리즘은 존재하지 않습니다. 최악의 경우, 백트래킹은 회로를 찾기 위해 최대 (n−1)! 크기의 탐색 트리를 탐색해야 합니다. 이것이 본 계산기가 입력을 20개 정점으로 제한하는 이유입니다. n이 약간만 증가해도 실행 시간이 폭발적으로 늘어나기 때문입니다.

실제로는 (1823년 Heinrich Warnsdorff가 기사의 여행 문제를 위해 고안한) Warnsdorff 휴리스틱을 통해 구조화된 그래프에서의 탐색 속도를 획기적으로 높일 수 있습니다. 각 단계에서 알고리즘은 아직 방문하지 않은 이웃 중 남은 미방문 이웃의 수가 가장 적은 정점으로 경로를 확장합니다. 이 탐욕적 규칙은 탐색이 막다른 길에 다다르는 것을 방지하며, 상태가 좋은 그래프에서는 백트래킹 없이 해밀턴 투어를 찾아내는 경우가 많습니다.

필요 조건 — 빠른 거부

비용이 많이 드는 탐색을 실행하기 전에, 계산기는 해밀턴 경로를 포함할 가능성이 없는 그래프를 미리 걸러냅니다.

• 연결성: 해밀턴 경로는 모든 정점을 방문해야 하므로 그래프는 정확히 하나의 연결 성분을 가져야 합니다. 유향 그래프의 경우, 화살표 방향을 무시한 약한 연결성이 필요합니다.
• 차수 (무향): 차수가 1인 정점은 최대 2개까지만 허용됩니다. 이들이 경로의 끝점이 될 수 있는 유일한 후보이기 때문입니다. 해밀턴 회로의 경우, 모든 정점의 차수는 최소 2여야 합니다.
• 차수 (유향): 해밀턴 경로의 경우, 진입 차수가 0인 정점은 최대 1개(시작점), 진출 차수가 0인 정점은 최대 1개(끝점)만 허용됩니다. 해밀턴 회로의 경우, 모든 정점은 진입 차수 ≥ 1 및 진출 차수 ≥ 1을 가져야 합니다.

이러한 규칙은 희망이 없는 많은 입력을 선형 시간 내에 거부하여 헛된 백트래킹 노력을 방지합니다.

충분 조건 — 고전 정리

여러 고전 정리는 단순 무향 그래프에서 해밀턴 회로를 보장하는 충분(필요는 아님) 조건을 제공합니다. 이들 중 하나라도 적용되면 계산기는 탐색을 실행하기도 전에 결과를 "보장됨(GUARANTEES)"으로 표시합니다(단, 증거 회로는 여전히 찾아 보여줍니다).

Dirac의 정리 (1952)

G가 n ≥ 3인 단순 무향 그래프이고 모든 정점의 차수가 최소 n / 2이면, G는 해밀턴 회로를 가집니다.

Ore의 정리 (1960)

인접하지 않은 모든 정점 쌍 u와 v에 대해 deg(u) + deg(v) ≥ n이면, G는 해밀턴 회로를 가집니다. Ore의 조건은 Dirac보다 엄격하지 않으므로, Ore의 정리는 Dirac의 정리가 성립하는 모든 경우를 포함합니다.

Dirac 또는 Ore의 조건을 충족하지 못한다고 해서 그래프에 해밀턴 회로가 없다는 의미는 아닙니다. 두 조건 모두 만족하지 않지만 해밀턴 회로를 가진 그래프는 매우 많습니다(예: 단순 n-회로는 최소 차수가 2이며, 이는 큰 n에 대해 n/2보다 훨씬 작습니다).

내부 탐색 알고리즘

사전 점검으로 결론이 나지 않을 때, 계산기는 그래프의 인접 표현에 대해 백트래킹 탐색을 실행합니다. 주요 전략:

1. 비트마스크 방문 집합: 방문한 정점들을 비트마스크로 저장합니다 (최대 20개 정점에 대해 빠른 O(1) 멤버십 테스트 가능).
2. Warnsdorff 휴리스틱: 경로 확장 시 남은 미방문 차수가 적은 순서대로 이웃을 시도하여 분기 발생을 최소화합니다.
3. 루트 선택: 해밀턴 회로의 경우 시작 정점 하나만 확인하면 됩니다(회로는 회전 불변). 해밀턴 경로의 경우 진출 차수가 낮은 순서(가장 희귀한 위치)대로 시작 정점을 시도합니다.
4. 단계 예산: 하드 캡을 설정하여 비정상적인 사례가 무한정 실행되는 것을 방지합니다. 예산이 소진되면 UI에 "시간 초과"로 보고됩니다.

해밀턴 vs 오일러

해밀턴 문제와 오일러 문제는 이름은 비슷하지만 근본적으로 다릅니다.

지원되는 입력 형식

간선 리스트

한 줄에 하나의 간선을 입력하거나 쉼표로 구분합니다. 지원되는 구분자: A-B, A B, A,B, A--B, A->B, A<-B. 유향 그래프임을 명시하려면 ->를 사용하세요.

인접 행렬

0/1 값의 정사각 행렬을 한 줄에 한 행씩 공백 또는 쉼표로 구분하여 입력합니다. '행렬 레이블' 필드에 선택적으로 레이블을 제공할 수 있으며, 제공하지 않으면 A, B, C...가 자동으로 사용됩니다.

이 검사기 사용 방법

1. 입력 형식 선택: 손으로 직접 작성한 작은 그래프는 '간선 리스트', 코드나 교재에서 복사한 데이터는 '인접 행렬'을 선택합니다.
2. 그래프 데이터 입력: 텍스트 영역에 그래프를 붙여넣습니다. 행렬 입력의 경우 필요에 따라 정점 레이블을 입력합니다.
3. 검사 항목 선택: 경로만, 회로만, 또는 한 번에 둘 다 검사할지 선택합니다.
4. 그래프 유형 선택: '자동 감지'는 화살표 스타일(->)이나 행렬의 대칭성을 통해 유향 여부를 판단합니다.
5. 해밀턴 검사 클릭: 결과 페이지에 판정 결과, 필요 조건 사전 점검, Dirac / Ore 충분 조건 테스트, 증거 경로(존재하는 경우), 대화형 시각화가 표시됩니다.
6. 증거 재생: 재생 / 단계 컨트롤을 사용하여 경로가 그래프 위에서 간선을 따라 밝혀지는 모습을 확인하세요.

활용 사례 — Petersen 그래프

유명한 Petersen 그래프(정점 10개, 간선 15개, 3-정규 그래프)는 해밀턴 경로는 있지만 해밀턴 회로는 없는 그래프의 대표적인 교재 예시입니다. 다음을 간선 리스트 필드에 붙여넣고 검사를 클릭해 보세요.

검사기는 해밀턴 경로(예: 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3)를 찾아 확인해 주지만, 전수 조사를 통해 시작점으로 돌아오는 회로는 없음을 확인해 줍니다. 이는 1890년대에 처음 증명된 결과입니다.

일반적인 응용 분야

• 라우팅 및 외판원 문제(TSP): 모든 TSP 경로는 완전 가중치 그래프의 해밀턴 회로입니다.
• 게놈 조립: 중첩된 리드(read)들로부터 DNA 시퀀스를 재구성하는 것은 중첩 그래프에서 해밀턴 경로로 모델링될 수 있습니다.
• 회로 설계: 배선 길이를 최소화하기 위해 PCB 상의 핀 순서를 정하는 문제.
• 게임 AI 및 퍼즐 해결: 체스판의 기사의 여행, 이코시안 게임.
• 스케줄링: 각 작업이 다음 작업으로 원활하게 전환되도록 작업 순서를 정하는 문제.
• 조합론 교육: 직접 손으로 풀 수 있는 작은 예시를 통해 NP-완전성을 설명하는 용도.

자주 묻는 질문

해밀턴 경로란 무엇인가요?

해밀턴 경로는 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로입니다. 1857년 정십이면체 그래프에서 이 문제를 연구한 William Rowan Hamilton의 이름을 따서 명명되었습니다. 이러한 경로의 존재 여부를 결정하는 것은 NP-완전 문제이므로, 모든 그래프에 대해 다항 시간 내에 해결할 수 있는 알고리즘은 알려져 있지 않습니다.

해밀턴 회로는 해밀턴 경로와 어떻게 다른가요?

해밀턴 회로는 시작 정점으로 다시 돌아와 모든 정점을 정확히 한 번씩 방문하는 폐루프를 형성하는 해밀턴 경로입니다. 모든 해밀턴 회로는 해밀턴 경로를 포함하지만(마지막 간선을 제외하면 됨), 그 반대는 성립하지 않습니다. 많은 그래프가 해밀턴 경로는 가지지만 해밀턴 회로는 가지지 않습니다.

Dirac의 정리는 무엇을 말하나요?

Dirac의 정리(1952)에 따르면, 정점의 개수 n이 3 이상인 단순 무향 그래프에서 모든 정점의 차수가 n/2 이상이면 해밀턴 회로를 포함합니다. 이는 충분 조건이지만 필요 조건은 아닙니다. Dirac 임계값을 충족하지 못하는 많은 그래프도 여전히 해밀턴 회로를 가질 수 있습니다.

Ore의 정리는 무엇을 말하나요?

Ore의 정리(1960)에 따르면, 정점의 개수 n이 3 이상인 단순 그래프에서 인접하지 않은 모든 정점 쌍 u와 v에 대해 두 정점의 차수 합이 n 이상이면 해당 그래프는 해밀턴 회로를 가집니다. Ore의 조건은 Dirac의 조건보다 약하므로, Dirac의 정리가 적용되는 모든 경우에 Ore의 정리도 적용됩니다.

왜 탐색이 20개 정점으로 제한되나요?

해밀턴 경로 및 회로 결정 문제는 NP-완전 문제입니다. 최악의 경우 실행 시간은 정점 수에 따라 기하급수적으로 증가합니다. 가지치기와 Warnsdorff 휴리스틱을 통해 본 계산기는 정점 20개까지의 많은 소규모 그래프를 빠르게 처리하지만, 더 복잡한 사례는 타임아웃이 발생할 수 있습니다. 20개 정점을 초과하는 경우 Concorde 또는 정수 계획법 수식과 같은 전문 솔버를 사용해야 합니다.

Warnsdorff 휴리스틱이란 무엇인가요?

1823년 기사의 여행(Knight's tour) 문제를 위해 제안된 Warnsdorff의 규칙은 매 단계마다 방문하지 않은 이웃 정점 중 남은 이웃 정점 수가 가장 적은 다음 정점을 방문해야 한다는 것입니다. 이 탐욕적 방식은 실제 백트래킹 트리를 획기적으로 가지치기하며, 정규 그래프에서 백트래킹 없이 해밀턴 경로를 찾는 경우가 많습니다.

이 도구는 모든 해밀턴 경로를 찾아주나요?

아니요. 경로 또는 회로가 존재하는 경우 하나의 증거 시퀀스만 찾습니다. 해밀턴 경로의 총 개수를 세는 것은 그 자체로 #P-완전 문제이며, 결정 문제보다 훨씬 어렵습니다. 열거(enumeration)를 위해서는 전용 도구나 정수 계획법 솔버가 더 적합합니다.

더 읽어보기

• 해밀턴 경로 — Wikipedia (영문)
• 해밀턴 경로 문제 — Wikipedia (영문)
• 해밀턴 회로에 대한 Dirac의 정리 — Wikipedia (영문)
• Ore의 정리 — Wikipedia (영문)
• Warnsdorff의 규칙 — Wikipedia (영문)

고급 수학 연산 도구:

• 앤티로그 계산기
• 베타 함수 계산기
• 이항 계수 계산기
• 이항 확률 분포 계산기
• 비트-계산기 추천
• 중심극한정리 계산기
• 조합 계산기
• 상보 오차 함수 계산기
• 복소수 계산기
• 엔트로피 계산기
• 오차 함수 계산기
• 지수 붕괴 계산기 - 높은 정밀도
• 지수 성장 계산기 높은 정밀도
• 지수 적분 계산기
• 지수-계산기-높은-정확도
• 팩토리얼 계산기 추천
• 감마 함수 계산기
• 황금비율 계산기
• 반감기 계산기
• 백분율 성장 계산기 추천
• 순열 계산기
• 포아송 분포 계산기
• 다항식 근 계산기와 상세한 단계
• 확률 계산기 추천
• 확률 분포 계산기
• 비율 계산기
• 이차 공식 계산기
• 공학용 계산기 추천
• 과학적 표기법 계산기
• 유효숫자 계산기 새로운
• 큐브 합계 계산기
• 연속 숫자의 합 계산기
• 제곱합 계산기
• 진리표 생성기
• 집합론 계산기
• 벤 다이어그램 생성기 (3세트)
• 중국인의 나머지 정리 계산기
• 오일러 피 함수 계산기
• 확장 유클리드 알고리즘 계산기
• 모듈러 곱셈 역원 계산기
• 연분수 계산기
• 다익스트라 최단 경로 계산기
• 최소 신장 트리 계산기
• 그래프 차수열 검증기
• 완전순열 (부분계승) 계산기
• 스털링 수 계산기
• 비둘기집 원리 계산기
• 마르코프 체인 정상 상태 계산기
• 반올림 계산기 새로운
• 음이항분포 계산기 새로운
• 중복순열 계산기 새로운
• 모듈러 거듭제곱 계산기 새로운
• 원시근 계산기
• 불 대수 간소화기 새로운
• 카르노 맵 (K-Map) 솔버 새로운
• 그래프 채색 계산기 새로운
• 위상 정렬 계산기 새로운
• 인접 행렬 계산기 새로운
• 포함배제 계산기 새로운
• 선형 계획법 솔버 새로운
• 외판원 문제 솔버 (TSP) 새로운
• 해밀턴 경로 검사기 (Hamiltonian Path Checker) 새로운
• 평면 그래프 검사기 새로운
• 네트워크 플로우 계산기 (최대 유량) 새로운
• 안정된 결혼 문제 해결기 새로운
• 군론 위수 계산기 새로운
• 환과 체 계산기 새로운