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

充分条件1

定理7－4．4 设 $G$ 是 $n$ 阶无向简单图，若对于 $G$ 中每一对结点 $v_j, v_i$ 均有 $d\left(v_j\right)+d\left(v_i\right) \geq_{n-1}$ ，则 $G$ 中存在汉密尔顿通路。证明 首先证明 $G$ 是连通图。

否则 $G$ 至少有两个连通分支，
设 $G_1, G_2$ 是阶数为 $n_1, n_2$ 的两个连通分支，
设 $v_1 \in V\left(G_1\right), v_2 \in V\left(G_2\right)$ ，因为 $G$ 是简单图，所以

$$
d_G\left(v_1\right)+d_G\left(v_2\right)=d_{G 1}\left(v_1\right)+d_{G 2}\left(v_2\right) \leq n_1-1+n_2-1 \leq n-2 < n-1
$$
　这与已知矛盾，所以G必为连通图。
  ![图片](/uploads/2025-01/43938a.jpg)
  
  
  下面证G中存在汉密尔顿通路。
设Г＝v1v2…vl为G中一条通路，显然有l≤n。 
(1)若l＝n，则Г为G中汉密尔顿通路。
(2)若l＜n，这说明G中还存在着Г外的顶点。
	如果v1或vl邻接于不在Г通路上的顶点，则可以包含该顶点，扩展Г为边长l+1的通路，一直扩展，若最终长度达到n则找到汉密尔顿通路；否则最终路长<n时，必有v1和vl只邻接于在Г通路上的顶点。可以证明G中存在经过Г上所有顶点的回路。
	(a)	若v1与vl相邻，即(v1,vl)∈E(G)，
		则Г∪(v1,vl)为满足要求的回路。

充分条件1
（b）若 $v_1$ 与 $v_l$ 不相邻，设 $v_1$ 与 $\Gamma$ 上的 $v_{i 1}, v_{i 2}, \ldots, v_{i k}$ 相邻，若 $v_l$ 与 $v_{i 1-1}, v_{i 2-1}, \ldots, v_{i k-1}$ 之一相邻，例如 $v_{i r-1}$ ，则回路 $C=V_1 V_2 \ldots V_{i r-1} V_1 V_{1-1} \ldots V_i \ldots V_{i r} V_1$ 过 $\Gamma$ 上的所有顶点。
 ![图片](/uploads/2025-01/101da7.jpg)
 
 若 $v_l$ 不与 $v_{i 1-1}, v_{i 2-1}, \ldots, v_{i k-l}$ 任一个相邻，则 $v_l$ 至多邻接于 $l-1-k$ ，即 $d\left(v_i\right) \leq l-k-1, d\left(v_j\right)+d\left(v_i\right) \leq k+l-k-1<n-1$ ，与已知矛盾。
 
 
 （c）下面证明存在比 $\Gamma$ 更长的路径。因为 $l<n$ ，所以 $C$ 外还有顶点，由 $G$ 的连通性可知，存在 $v_{l+1} \in V(G)-V(C)$ 与 $C$上某顶点 $v_t$ 相邻，见下图所示。
 ![图片](/uploads/2025-01/a4fd2d.jpg)
删除边 $\left(v_{t-1}, v_t\right)$ 得路径 $\Gamma^{\prime}=v_{t-1} \ldots v_1 V_{i r} \ldots v_1 V_{i r-1} \ldots v_t V_{l+1}$比 $\Gamma$ 长度大 $1(1+1)$ ，顶点重新排序 $\Gamma^{\prime}=V_1 V_2 \ldots V_l V_{l+1}$对 $\Gamma^{\prime}$ 重复 $(a) \sim(c)$ ，在有限步内一定得到 $G$ 的汉密尔顿通路。

定理7－4．5（推论）设 $G$ 为 $n(n \geq 3)$ 阶无向简单图，若对于 $G$ 中任意两个不相邻的顶点 $v_i, v_i$ ，均有 $d\left(v_i\right)+d\left(v_j\right) \geq n$ ，则 $G$ 中存在汉密尔顿回路，从而 $G$为汉密尔顿图。
证明 由定理7－4．4可知，$G$ 中存在汉密尔顿通路，设 $\Gamma=v_1 v_2 \ldots v_n$ 为 $G$ 中一条汉密尔顿通路，
若 $v_1$ 与 $v_n$ 相邻，设边 $e=\left(v_1, v_n\right)$ ，则 $\Gamma \cup\{e\}$ 为 $G$ 中汉密尔顿回路。
若 $v_1$ 与 $v_n$ 不相邻，同定理7－4．3证明中的（2）类似，可证明存在过 $\Gamma$ 上各顶点的圈，即为 $G$ 中的汉密尔顿回路。

## 例7-4.7 判断是否是汉密尔顿图
 ![图片](/uploads/2025-01/9d32a0.jpg)
 
 
 思考：下图中哪些是(半)汉密尔顿图？
  ![图片](/uploads/2025-01/aaafe0.jpg)
  
  (1)存在汉密尔顿回路，所以(1)为汉密尔顿图。
(2)取V1＝{a,b,c,d,e}，从图中删除V1得7个连通分支，由定理可知，不是汉密尔顿图，也不是半汉密尔顿图。
(3)取V1＝{b,e,h}，从图中删除V1得4个连通分支，由定理可知，它不是汉密尔顿图。但存在汉密尔顿通路，所以是半汉密尔顿图。

`例`设 $n \geq 2$ ，有 $2 n$ 个人参加宴会，每个人至少认识其中的 $n$ 个人，怎样安排座位，使大家围坐在一起时，每个人的两旁坐着的均是与他相识的人？

解每个人用一个顶点表示，若二人相识，则在其所表的顶点间连边。这样得到一个 $2 n$ 阶的无向图，因为对于任意的两个顶点 $u, v$ ，有：$d(u)+d(v) \geq 2 n$ ，故图中存在一条汉密尔顿回路，这条回路恰好对应一个座位的适当安排。

`例`考虑在七天内安排七门课程的考试，使得同一位教师所担任的两门课程考试不排在接连的两天中。试证明，如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。

证明：设G为具有七个顶点的图，每个顶点对应于一门课程考试，如果这两个顶点对应的课程考试是由不同教师担任的，那么这两个顶点之间有一条边。因为每个教师所任课程数不超过4，故每个顶点的度数至少是7-4=3，任意两个顶点的度数之和至少是6，故G总是包含一条哈密尔顿通路，它对应于一个七门考试科目的一个适当的安排。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：彼得森(Petersen)图

下一篇：平面图的基本概念

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