最后更新: 2025-01-21 17:13 查看: 102 次纠错评论(0) 课件开VIP

汉密尔顿图

历史背景：汉密尔顿周游世界问题
汉密尔顿周游世界问题——从正十二面体的一个顶点出发，沿着棱前进，经过全部的二十个顶点一次且仅一次，最后回到出发点。

![图片](/uploads/2025-01/3b7af5.jpg)
 
 定义7-4.3 给定图G，若存在一条路，经过所有的结点一次且仅一次，称为汉密尔顿路；若存在经过图中所有结点一次并且仅一次的回路称为汉密尔顿回路。
具有哈密尔顿回路的图称为汉密尔顿图
具有哈密顿路但不具有哈密顿回路的图称为半汉尔密顿图

例7-4.4 判断下图是否(半)汉密尔顿图
 ![图片](/uploads/2025-01/40fd5d.jpg)
 (1)(2)是汉密尔顿图。
(3)是半汉密尔顿图。
(4)既不是汉密尔顿图，也不是半汉密尔顿图。

定理7－4．3 设无向图 $G=\langle V, E\rangle$ 是汉密尔顿图，对于任意 $S \subset V$ ，且 $S \neq \varnothing$ ，均有 $W ( G -S) \leq|S|$ ，即G－S连通分支数不超过 $S$ 结点数。

证明 设 C 为 G 中任意一条汉密尔顿回路，
1）当 $S$ 中顶点在 $C$ 上均不相邻时，$W(C-S)$ 达到最大值 $|S|$ ，
2）当 $S$ 中结点在 $C$ 上有相邻的情况时，均有 $W(C-S)<|S|$ ，所以有 $W ( G - S ) \leq| S |$ 。

而C是 G 的生成子图，所以有 $W ( G - S ) \leq W ( C - S ) \leq| S |$ 。
说明 本定理的条件是汉密尔顿图的必要条件，但不是充分条件。若一个图不满足定理中的条件，它一定不是汉密尔顿图。

例7-4.5 证明：若G中有割点或桥，则G不是哈密顿图。
证明（1）证明若 $G$ 中有割点，则 $G$ 不是哈密顿图。
设 $v$ 为连通图 $G$ 中一个割点，则 $V^{\prime}=\{v\}$ 为 $G$ 中的点割集，而

$$
p\left(G-V^{\prime}\right) \geq 2>1=\left|V^{\prime}\right|
$$

由定理15．6可知 $G$ 不是哈密顿图。
（2）证明若 $G$ 中有桥，则 $G$ 不是哈密顿图。
设 $G$ 中有桥，$e=(u, v)$ 为其中的一个桥。
若 $u, v$ 都是悬挂边，则 $G$ 为 $K 2, ~ K 2$ 不是哈密顿图。
若 $u, v$ 中至少有一个，比如 $u, d(u) \geq 2$ ，由于 $e$ 与 $u$ 关联，$e$ 为桥，所以 $G-u$ 至少产生两个连通分支，于是 $u$ 为 $G$ 中割点。
由（1）的讨论可知，$G$ 不是哈密顿图。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：欧拉图

下一篇：彼得森(Petersen)图

本文对您是否有用？有用 (0) 无用 (0)