科数网
学习首页
题库
高中数学
高等数学
线性代数
概率统计
实变函数
复变函数
离散数学
数论
群论
公式
高中数学公式
高等数学公式
线性代数公式
概率论公式
初中数学公式
关于
高中
高数
线性
公式
高中数学公式
高等数学公式
线性代数公式
概率论公式
初中数学公式
游客,
登录
注册
在线学习
拓扑学
欧拉图与哈密尔顿图
哈密顿图
最后
更新:
2023-11-07 19:28
●
参与者
查看:
215
次
纠错
分享
参与项目
词条搜索
哈密顿图
## 定义 哈密顿路径: 在无向图 $G$ 中包含其所有顶点的初级路径 哈密顿回路:在无向图 $G$ 中包含其所有顶点的初级回路 哈密顿图: 具有哈密顿回路的无向图 例1: 下图中(a),哈密顿提出的「周游世界」的游戏。把一个正十二面体的二十个顶点看成地球上的二十个城市。要求游戏者沿棱线走,寻找一条经过所有结点一次且仅一次的回路,(b)是其哈密顿图,哈密顿回路由实线标出。 ![图片](/uploads/2023-10/0e7bc2.jpg) 例2:下图中,图(a)(b)中有哈密顿回路,为哈密顿图,图(c)中有哈密顿路径,(d)中两者均无 ![图片](/uploads/2023-10/55525f.jpg) PS:欧拉图与哈密顿图对比,欧拉图遍历的是边,而哈密顿图遍历的是结点。 ## 哈密顿图的判定 对于哈密尔顿图的判定,只能给出若干必要条件或充分条件,没有充要条件。 1.必要条件 定理 (1): 若 $G$ 是哈密尔顿图,则对于结点集 $V(G)$ 的任一非空真子集 $S \subset V(G)$ 有 $\omega(G-S) \leq|S|$ 。其中 $G-S$ 表示在 $G$ 中删去 $S$ 中的结点后所构成的图, $\omega(G-S)$ 表示 $G-S$ 的连通分支数。 证明: 设 $C$ 是 $G$ 的一条哈密顿回路, $C$ 视为 $G$ 的子图,在回路 $C$ 中,每删去 $S$ 中的一个结点,最多增加一个连通分支,且删去 $S$ 中的第一个结点时分支数不变,所以有 $\omega(C-S) \leq|S|$。又因为 $C$ 是 $G$ 的生成子图,所以 $C-S$ 是 $G-S$ 的生成子图,且 $\omega(G-S) \leq \omega(C-S)$ ,因此 $\omega(G-S) \leq|S|$ 。 推论: 若 $G$ 含有哈密尔顿路径,即半哈密尔顿图,则对于结点集 $V(G)$ 的任一非空真子集 $S \subset V(G)$ 有 $\omega(G-S) \leq|S|+1$ 。 思路:因为不是回路,在哈密尔顿通路上删除第一个点,最多可以产生两个分支。 PS:哈密顿图的必要条件,可用来判定某些图不是哈密尔顿图,是破坏条件。 例3: 下图中,(a)不是哈密尔顿图。(a)中如果删除中间三个白点,即 $|S|=3$ ,而此时 $\omega(G-S)=4$ ,见图(b)。(c)虽然满足定理(1),但不是哈密顿图。 ![图片](/uploads/2023-10/de9413.jpg) 2. 充分条件 首先引入扩大路径法: 设 $G=\langle V, E\rangle$ 为 $n$ 阶无向图, $\Gamma_l$ 为 $G$ 中一条初级路径。若此路径的起点或终点,与路径外的结点相邻,就将他们扩充到路径中,重复这一过程,直到路径的两端不与路径外的结点相邻为止。最后得到的路径 $\Gamma_{l+k}$ 为一条极大路径 (由长度 $l$ 扩充到 $l+k$ ,且不唯一),并称使用此种方法证明问题的方法为扩大路径法。 例3: 设 $G$ 为 $n(n \geq 3)$ 阶无向简单图,最小度 $\delta \geq 2$ 。证明 $G$ 中存在长度 $\geq \delta+1$ 的回路。 证明: 设 $\Gamma_l=v_0 v_1 \ldots v_l$ 是 $G$ 中的一条极大路径。由极大路径的定义知, $v_0$ 不与 $\Gamma_l$ 外的结点相邻,而 $d\left(v_0\right) \geq \delta$ ,所以至少存在 $\delta$ 个 $\Gamma_l$ 上的结点与 $v_0$ 相邻。设 $v_\delta$ 是与 $v_0$ 相邻,且在 $\Gamma_l$ 上与 $v_0$ 最远的结点,则路径 $v_0 v_1 \ldots v_\delta$ 的长度 $\geq \delta$ 。于是, $v_0 v_1 \ldots v_\delta v_0$ 为长度 $\geq \delta+1$ 的回路。 定理 (2): 设图 $G$ 是 $n$ 阶的无向简单图 $(n \geq 3)$ ,如果 $G$ 中每一对不相邻的结点 $u, v$ 均有 $d(u)+d(v) \geq n-1$ ,则 $G$ 中存在哈密顿路径。 证明: (1) 证明 $G$ 是连通图 反证法: 若 $G$ 不是连通图,则至少存在两个分支。设连通分支 $G_1, G_2$ 的阶数为 $n_1, n_2$ 。不妨设 $u \in V\left(G_1\right), v \in V\left(G_2\right)$ ,则有 $d(u)+d(v) \leq\left(n_1-1\right)+\left(n_2-1\right)=n-2$ ,此与题设矛盾,所以 $G$ 是连通图。 (2) 证明 $G$ 中存在哈密顿路径 设 $\Gamma_l=v_1 v_2 \ldots v_l$ 为 $G$ 中的一条极大路径。 (1) 若 $l=n$ ,则找到一条哈密顿路径 $\Gamma_l$ ; (2) 若 $l<n$ ,则必定存在一点 $v_{o u t}$ 与 $\Gamma_l$ 上除 $v_1, v_l$ 外的端点相连。此时,若存在圈 $C$ 刚好经过 $\Gamma_l$ 上的所有点,则圈 $C$ 又可与 $v_{o u t}$ 组合成更长的极大路径 $\Gamma_{l+1}$ 。 重复上述(1)(2)过程,最终找到一条哈密顿路径。 下面证明,存在回路 $C$ 经过 $\Gamma_l$ 上所有的点。 (1) 若 $v_1, v_l$ 相邻,则容易找到回路 $C$; (2) 若 $v_1, v_l$ 不相邻,设 $v_1$ 与 $\Gamma_l$ 上的 $v_{i_1}=v_2, v_{i_2}, \ldots, v_{i_k}$ 相邻,则 $k \geq 2$ 。否则, $d\left(v_1\right)+d\left(v_l\right)=1+l-2<n-2$ 。 又 $v_l$ 至少与 $v_{i_2-1}, v_{i_3-1} \ldots, v_{i_k-1}$ 之一相邻,否则, $d\left(v_1\right)+d\left(v_l\right)=k+[l-2-(k-1)]<n-2$ 。设 $v_l$ 与 $v_{i_r-1}$ 相邻,则得到回路 $C=\left(v_1 v_2 \ldots v_{i_r-1} v_l v_{l-1} \ldots v_{i_r} v_1\right) 。$ ![图片](/uploads/2023-10/c9f134.jpg) 定理 (3): 设图 $G$ 是 $n$ 阶的无向简单图 $(n \geq 3)$ ,对于 $G$ 中每一对不相邻的结点 $u, v$ 均有 $d(u)+d(v) \geq n$ ,则 $G$ 是哈密顿图。 但不满足定理(2)(3)的,不一定不是哈密顿图。如下图,不满足定理(2)(3),但是哈密顿图。 ![图片](/uploads/2023-10/77528f.jpg)
上一篇:
欧拉图
下一篇:
没有了
本文对您是否有用?
有用
(
0
)
无用
(
0
)
如果本文对你有用,我们感觉很高兴, 随着规模的增长,我们需要更多资金支持, 欢迎您
打赏作者
索引
高中数学(教程)
高中数学(公式)
高等数学(教程)
高等数学(公式)
线性代数(教程)
线性代数(公式)
赞助商:
启明星会议室预约
题库
关于本站
广告赞助
科数网是专业专业的数学网站。