概述
复习离散5555
哈密顿图
-
哈密顿道路：经过每个节点的基本道路
-
哈密顿圈：经过每个节点的回路
-
哈密顿图：具有哈密顿圈的图
-
必要条件：
- 哈密顿图 G ( V , E ) ⇒ G(V,E)Rightarrow G(V,E)⇒任意 V V V 的非空子集 S S S 都有 ω ( G − S ) < = ∣ S ∣ omega(G-S)<=|S| ω(G−S)<=∣S∣
- 哈密顿圈 C C C ， ∑ i = 1 n ( i − 2 ) ( f i ( 1 ) − f i ( 2 ) ) = 0 sum_{i=1}^{n}(i-2)left(f_{i}^{(1)}-f_{i}^{(2)}right)=0 ∑i=1n(i−2)(fi(1)−fi(2))=0，其中 f i ( 1 ) f_{i}^{(1)} fi(1) 和 f i ( 2 ) f_{i}^{(2)} fi(2) 分别是含在圈 C C C 内部和外部的 i i i 度面的数目。
-
充分条件：
- n ≥ 3 ngeq 3 n≥3 的简单图， ∀ u , v ∈ V , f ( u ) + f ( v ) ≥ n ⇒ forall u,v in V,f(u)+f(v)geq nRightarrow ∀u,v∈V,f(u)+f(v)≥n⇒ 哈密顿图
- n n n 阶简单图 ∀ u , v ∈ V , f ( u ) + f ( v ) ≥ n − 1 ⇒ forall u,v in V,f(u)+f(v)geq n-1Rightarrow ∀u,v∈V,f(u)+f(v)≥n−1⇒ 图中有哈密顿道路
-
充要条件：简单图是哈密顿图 ⇔ Leftrightarrow ⇔图的闭包图是哈密顿图
分枝界定法
精确解，不复杂的图
- 消去操作：每行找最小元，同行减去；每列找最小元，同列减去；减去的数累和得到下界。
- 第一行找最小元，分类讨论：
- 包含在最优解中：
- 将所在行列删去，最小元对称位置（指原矩阵中的对称位置）的元设为正无穷
- 继续操作剩下的矩阵
- 不包含在最优解中：查看当前值是否最优，不是的话暂停搜索
- 将该元设为正无穷
- 对剩下矩阵进行消去操作
- 包含在最优解中：
- 重复以上操作，每次都选取当前的最优解
最后
以上就是眯眯眼电灯胆为你收集整理的【离散数学】【图论】哈密顿图的全部内容，希望文章能够帮你解决【离散数学】【图论】哈密顿图所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复