해밀턴 경로·사이클 판정기
정점과 간선을 넣으면 모든 정점을 정확히 한 번씩 지나는 경로(사이클)가 있는지 백트래킹으로 완전탐색해 찾습니다. 디락·오레 정리 같은 충분조건도 함께 보여줍니다.
간선 목록 (한 줄에 하나)
«A B»는 A와 B를 잇는 선(방향 없음)입니다. 완전탐색이라 정점이 11개를 넘으면 계산할 수 없습니다.
해밀턴 경로
있습니다
A → B → C → D
디락 정리(n≥3, 모든 차수≥n/2): 만족
오레 정리(이웃 아닌 모든 쌍의 차수합≥n): 만족
계산 방법
- 1간선을 한 줄에 하나씩 «A B» 형태로 입력합니다.
- 2해밀턴 경로·사이클이 있는지, 있다면 실제 경로가 무엇인지 확인합니다.
- 3디락·오레 정리 충분조건을 만족하는지도 함께 봅니다.
- 4예시(사이클·별 모양·페테르센 그래프)를 눌러 결과가 어떻게 갈리는지 비교합니다.
자주 묻는 질문
그래프의 모든 정점을 정확히 한 번씩 지나는 경로입니다. 마지막 정점이 시작 정점과도 이어져 있으면 해밀턴 사이클(순환)이라고 부릅니다.
오일러 경로는 모든 «간선»을 한 번씩 지나는 문제로, 정점의 차수만 세면 즉시 판정됩니다(홀수 차수 정점이 0개면 회로, 2개면 경로). 해밀턴 경로는 모든 «정점»을 한 번씩 지나는 문제인데, 일반적인 빠른 판정법이 알려져 있지 않은 NP-완전 문제라 이 계산기는 백트래킹으로 완전탐색합니다.
완전탐색이라 최악의 경우 탐색량이 정점 수의 계승(n!)에 가깝게 늘어납니다. 정점이 조금만 늘어도 계산이 급격히 느려지기 때문에 실용적인 범위로 제한했습니다.
완전탐색 없이도 해밀턴 사이클이 «있다»고 보장해 주는 충분조건입니다. 디락 정리(1952)는 정점이 3개 이상이고 모든 정점의 차수가 정점 수의 절반 이상이면 사이클이 있다고 말하고, 오레 정리(1960)는 이웃이 아닌 모든 정점 쌍의 차수 합이 정점 수 이상이면 사이클이 있다고 말합니다. 디락 조건을 만족하면 오레 조건도 자동으로 만족합니다.
아닙니다. 디락·오레 정리는 «충분조건»이지 «필요조건»이 아닙니다. 조건을 만족 못 해도 실제로는 경로나 사이클이 있을 수 있습니다. 페테르센 그래프가 대표적인 예로, 두 조건 모두 불만족이지만 실제로 해밀턴 경로는 있습니다(사이클은 없습니다).
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 백트래킹 완전탐색을 씁니다. 정점은 최대 11개까지 지원합니다.
- 경로는 시작 정점을 정하지 않고 모든 정점을 시작점으로 시도해 찾습니다.
- 디락·오레 정리는 해밀턴 «사이클»에 대한 충분조건입니다(둘 다 만족 못 해도 사이클이 있을 수 있습니다). 사이클이 있으면 그 사이클에서 간선 하나를 지운 것이 경로이므로 경로도 자동으로 있습니다.
- 작은 그래프(정점 8개 이하)에서는 순열을 모두 훑는 무식한 방법과 결과가 항상 같은지 확인했습니다.
- 입력한 값은 브라우저 안에서만 계산되며 서버로 전송되지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.