最后更新: 2025-01-21 17:51 查看: 41 次反馈刷题

充分条件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总是包含一条哈密尔顿通路，它对应于一个七门考试科目的一个适当的安排。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：彼得森(Petersen)图

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

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