哈密尔顿通路

郭子欣 · 2019-10-17 19:38:54 · 个人记录

Hamilton Path

definition

哈密尔顿通路(Hamilton Path) ： 经过图 G 中每个节点一次且仅一次的通路称为Hamilton通路

哈密尔顿回路(Hamilton Circuit)： 经过图 G 中每个节点一次且仅一次的回路称为Hamilton回路

哈密尔顿图(Hamiltonian Graph)：存在 Hamilton 回路的图称为 Hamilton 图

充分条件

G=(V, E)是具有n个节点的简单无向图(|V|=n)，如果对于任意的两个不相邻的节点u, v\in V，均有deg(u)+deg(v)\ge n-1，则G中一定存在Hamilton Path

proof

• 假设$G$有两个或两个以上的联通块。其中一个有$n_1$个节点，另一个有$n_2$个节点，对于$\forall v_1,v_2$分别属于这两个联通块，那么$deg(v_1)\le n_1-1$，$deg(v_2)\le n_2-1$，显然$deg(v_1)+deg(v_2)\le n_1-1+n_2-1\le n-2$与已知条件矛盾

• 存在Hamilton\space Path

  任取两点s,t 如果有节点v与s相邻，则将路径扩大为v\rightarrow s\rightarrow t并将v作为新的s重复进行至无法扩展，对t也进行同样的操作。

  设最终得到一条有k个节点的通路v_1\rightarrow v_2\rightarrow\dots\rightarrow v_k-1\rightarrow v_k

  1. 若k=n，则该通路即为Hamilton\space Path

  2. 若k<n，此时可以证明存在仅通过这k个点的回路

     假设不存在满足条件的v_r，则deg(v_1)\le k-1-deg(v_k)，那么deg(v_1)+deg(v_k)\le k-1<n-1，与已知条件矛盾

     如图则为符合条件的回路

  3. 在2情况下存在比当前更长的通路，证明如下：

     

  重复操作直到k=n即可得到一条Hamilton\space Path

Ore's Theorem

G=(V, E) 是具有n个节点的简单无向图，如果对于任意两个不相邻的节点u, v\in V，均有deg(u)+deg(v)\ge n，则G中一定存在Hamilton circuit

proof:

同上证明并得到一条Hamilton\space Path

1. v_1$与$v_n$相邻，则恰好为一条$Hamilton circuit
2. 假设不存在满足条件的$v_r$，则$deg(v_1)\le n-1-deg(v_n)$，那么$deg(v_1)+deg(v_n)\le n-1$，与已知条件矛盾

得证