【离散数学】【图论】哈密顿图
·
复习离散5555
哈密顿图
-
哈密顿道路：经过每个节点的基本道路
-
哈密顿圈：经过每个节点的回路
-
哈密顿图：具有哈密顿圈的图
-
必要条件：
- 哈密顿图G(V,E)⇒G(V,E)\RightarrowG(V,E)⇒任意VVV 的非空子集SSS 都有ω(G−S)<=∣S∣\omega(G-S)<=|S|ω(G−S)<=∣S∣
- 哈密顿圈CCC ， ∑i=1n(i−2)(fi(1)−fi(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，其中 fi(1)f_{i}^{(1)}fi(1) 和 fi(2)f_{i}^{(2)}fi(2) 分别是含在圈 CCC 内部和外部的 iii 度面的数目。
-
充分条件：
- n≥3n\geq 3n≥3 的简单图，∀u,v∈V,f(u)+f(v)≥n⇒\forall u,v \in V,f(u)+f(v)\geq n\Rightarrow∀u,v∈V,f(u)+f(v)≥n⇒ 哈密顿图
- nnn 阶简单图∀u,v∈V,f(u)+f(v)≥n−1⇒\forall u,v \in V,f(u)+f(v)\geq n-1\Rightarrow∀u,v∈V,f(u)+f(v)≥n−1⇒ 图中有哈密顿道路
-
充要条件：简单图是哈密顿图⇔\Leftrightarrow⇔图的闭包图是哈密顿图
分枝界定法
精确解，不复杂的图
- 消去操作：每行找最小元，同行减去；每列找最小元，同列减去；减去的数累和得到下界。
- 第一行找最小元，分类讨论：
- 包含在最优解中：
- 将所在行列删去，最小元对称位置（指原矩阵中的对称位置）的元设为正无穷
- 继续操作剩下的矩阵
- 不包含在最优解中：查看当前值是否最优，不是的话暂停搜索
- 将该元设为正无穷
- 对剩下矩阵进行消去操作
- 包含在最优解中：
- 重复以上操作，每次都选取当前的最优解
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)