Hamiltonian Cycle ↔ TSP

이 환원은 정말 구조가 완벽하게 맞아떨어지는 대표적인 NP-완전 ↔ NP-완전 환원이고,

문제 간의 핵심 구조가 거의 1:1로 대응되기 때문에

이걸 보면 NP-완전 환원이 단순한 문제가 아니라는 걸 직관적으로 깨닫게 된다.

 

---

 

목적

 

* Hamiltonian Cycle:

  → 그래프에서 모든 정점을 정확히 한 번씩 방문하고 처음으로 돌아오는 경로가 존재하는가?

 

* TSP (결정판):

  → 주어진 거리 행렬이 있을 때, 모든 도시를 한 번씩 방문하는 순회 경로의 총 비용이 B 이하인가?

 

---

 

환원 개요:

 

> Hamiltonian Cycle 문제를 → TSP 문제로 환원

> → 즉, 순수한 "존재 여부" 문제를

> → 비용 조건이 붙은 최적화 문제 형태로 바꾸는 것.

 

---

 

환원 과정 요약

 

입력: 무방향 그래프 $G = (V, E)$

 

정점 수: $n$

 

만들 TSP 인스턴스:

 

* 도시 수: $n$개 (정점 = 도시)

* 거리 행렬 $D[i][j]$ 설정:

 

\[
D[i][j] = 
\begin{cases}
1 & \text{if } (i, j) \in E \\
2 & \text{otherwise}
\end{cases}
\quad\text{and}\quad B = n
\]

 

→ 즉, 원래 그래프에 간선이 있는 곳엔 거리 1,

없는 곳엔 일부러 더 먼 거리 2를 부여한다.

 

---

 

목표 경로 길이 $B = n$

 

→ TSP 문제: \*\*길이 합이 $\le n$\*\*인 해밀턴 경로가 존재하는가?

 

---

 

환원의 핵심 아이디어

 

* 원래 그래프 $G$에 **해밀턴 순환이 있다면**

  → $n$개의 간선으로 이뤄진 경로 → 모두 간선이므로 거리 총합 = $n$

 

* 해밀턴 순환이 없다면

  → 순회 경로 중 반드시 거리 2가 최소 하나 포함됨

  → 총합은 $> n$

 

---

 

결론: TSP가 길이 $\le n$인 해를 가지는지 판단하면

 

→ 원래 그래프에 해밀턴 사이클이 존재하는지 **정확히 판별 가능**

 

---

 

이 환원이 대단한 이유

요소	이유
구조 대응	정점 ↔ 도시, 간선 ↔ 거리
조건 대응	해밀턴 경로 ↔ TSP 거리 합 조건
논리 ↔ 수치	"존재 여부"를 "최소합 조건"으로 변환
정수 거리	TSP가 **정수로 환원되는 것도 장점** (정확도 이슈 없음)

---

 

흥미로운 점

 

* "논리적 경로 존재성" ↔ "최적화 경로의 비용 조건"

  구조가 NP-완전 논리 ↔ 조합 최적화 문제 간 환원의 교과서급 예시

* 수학적으로도 임계값 $n$ 설정이 깔끔함

* 실용적으로는 이 구조를 근사 알고리즘 성능 판단 기준으로도 씀