Hamilton cycle Cycle|

最是人间留不住，朱颜辞镜花辞树。这篇文章主要讲述Hamilton cycle相关的知识，希望能为你提供帮助。

目录

1.1 Hamilton cycle
2.1 Directed Hamilton cycle reduces to Hamilton cycle
- 2.1.1 证明
3.1 3-satisfiability reduces to directed Hamilton cycle
- 3.1.1 3-satisfiability reduces to directed Hamilton cycle
- 3.1.2 烦人的证明又来了！
4.1 3-satisfiability reduces to longest path
5.1 TSP
- 5.1.1 HAM-CYCLE ≤ P TSP

1.1 Hamilton cycleHAMILTON-CYCLE. Given an undirected graph G = (V, E), does there exist a
cycle Γ that visits every node exactly once?
一个有解的图，一个没有解的图如下：

文章图片

文章图片

2.1 Directed Hamilton cycle reduces to Hamilton cycleDIRECTED-HAMILTON-CYCLE. Given a directed graph G = (V, E), does there exist
a directed cycle Γ that visits every node exactly once?
关于有向哈密尔顿圈问题可以规约到哈密尔顿问题证明如下（DIRECTED-HAMILTON-CYCLE ≤ P HAMILTON-CYCLE.）：
Pf. Given a directed graph G = (V, E), construct a graph G? with 3n nodes.

文章图片

Lemma. G has a directed Hamilton cycle iff G? has a Hamilton cycle.
2.1.1 证明
Pf. ?

Suppose G has a directed Hamilton cycle Γ.
Then G? has an undirected Hamilton cycle (same order).

Pf. ?

Suppose G? has an undirected Hamilton cycle Γ?.
Γ? must visit nodes in G? using one of following two orders:
…, black, white, blue, black, white, blue, black, white, blue, …
…, black, blue, white, black, blue, white, black, blue, white, …
Black nodes in Γ? comprise either a directed Hamilton cycle Γ in G,
or reverse of one.

3.1 3-satisfiability reduces to directed Hamilton cycleConstruction. Given 3-SAT instance Φ with n variables xi and k clauses.

Construct G to have 2^n Hamilton cycles.
Intuition: traverse path i from left to right ? set variable xi = true.

文章图片

A problem:

文章图片

3.1.1 3-satisfiability reduces to directed Hamilton cycle
Construction. Given 3-SAT instance Φ with n variables xi and k clauses.

For each clause: add a node and 2 edges per literal.

文章图片

一个完整的实例图如下：

文章图片

3.1.2 烦人的证明又来了！
Lemma. Φ is satisfiable iff G has a Hamilton cycle
【Hamilton cycle】Pf. ?

Suppose 3-SAT instance Φ has satisfying assignment x*.
Then, define Hamilton cycle Γ in G as follows:

if x*i= true, traverse row i from left to right
if x*i= false, traverse row i from right to left
for each clause Cj , there will be at least one row i in which we are
going in “correct” direction to splice clause node Cj into cycle
(and we splice in Cj exactly once)

Pf. ?

Suppose G has a Hamilton cycle Γ.
If Γ enters clause node Cj , it must depart on mate edge.

nodes immediately before and after Cj are connected by an edge e ∈ E
removing Cj from cycle, and replacing it with edge e yields Hamilton
cycle on G –Cj

Continuing in this way, we are left with a Hamilton cycle Γ? in
G –C1 , C2 , …, Ck .
Set x*i= true if Γ? traverses row i left-to-right; otherwise,
set x*i= false. traversed in “correct” direction, and each clause is satisfied.

4.1 3-satisfiability reduces to longest pathPf 1. Redo proof for DIR-HAM-CYCLE, ignoring back-edge from t to s.
Pf 2. Show HAM-CYCLE ≤ P LONGEST-PATH
5.1 TSPTSP. Given a set of n cities and a pairwise distance function d(u, v),
is there a tour of length ≤ D ?
5.1.1 HAM-CYCLE ≤ P TSP