离散数学 中国地质大学 计算机学院 1 第 11 讲 哈密尔顿图 Hamilton Graph. 离散数学 中国地质大学 计算机学院 2 主要内容 1 哈密尔顿图 2 哈密尔顿图判定定理 3 建模：哈密尔顿图应用 ( 下节课讨论 ) 重点难点：哈密尔顿图判定定理.

Presentation on theme: "离散数学 中国地质大学 计算机学院 1 第 11 讲 哈密尔顿图 Hamilton Graph. 离散数学 中国地质大学 计算机学院 2 主要内容 1 哈密尔顿图 2 哈密尔顿图判定定理 3 建模：哈密尔顿图应用 ( 下节课讨论 ) 重点难点：哈密尔顿图判定定理."— Presentation transcript:

1 离散数学 中国地质大学 计算机学院 1 第 11 讲 哈密尔顿图 Hamilton Graph

2 离散数学 中国地质大学 计算机学院 2 主要内容 1 哈密尔顿图 2 哈密尔顿图判定定理 3 建模：哈密尔顿图应用 ( 下节课讨论 ) 重点难点：哈密尔顿图判定定理

3 离散数学 中国地质大学 计算机学院 3 11.1 哈密尔顿图 几个问题 1 在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞 车过每个提款机一次就能运送完钱钞？  货郎担问题  旅行商人问题 (Traveling Salesman Problem,TSP) 优化算法 —— 近似解  演化算法

4 离散数学 中国地质大学 计算机学院 4 11.1 哈密尔顿图 几个问题 1. 在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每 个提款机一次就能运送完钱钞？  货郎担问题  旅行商人问题 (TSP) 2. 考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排 在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求 的考试安排方案？  时间表问题 3. 国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回 到出发的棋盘格子？ 4. 在一个至少有 5 人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目 的，会议主持者希望每次会议每人两侧的人均与前次不同，这是否可行？请应用图 论知识进行论证。 5. 周游世界问题

5 离散数学 中国地质大学 计算机学院 5 11.1 哈密尔顿图 问题 1859 年爱尔兰数学家威廉 · 哈密尔顿（ Sir William Hamilton ）发明了一个小游戏玩具：一个木刻的正十二 面体，每面系正五角形，三面交于一角，共有 20 个角， 每角标有世界上一个重要城市。哈密尔顿提出一个问题： 要求沿正十二面体的边寻找一条路通过 20 个城市，而每 个城市只通过一次，最后返回原地。哈密尔顿将此问题称 为周游世界问题。游 戏 ) 求解 抽象为图论问题 哈密尔顿给出了肯定回答，该问题的解是存在的  哈密尔顿回路 ( 圈 )  哈密尔顿图 运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题

6 离散数学 中国地质大学 计算机学院 6 11.1 哈密尔顿图 In 1863, The American National Academy of Sciences appointed an Irishman, Dublin-born William Rowan Hamilton, its first Foreign Associate: he was considered by them to be the greatest of living scientists. William was born on the stroke of midnight on 3-4 August 1805. He was an infant prodigy, and he was unbeaten in every exam in both classics and science at Trinity College Dublin. Before he graduated he was appointed Royal Astronomer of Ireland, living at Dunsink Observatory. He made important contributions to theoretical physics and to mathematics.¼ he received a knighthood in 1835. Hamilton graphs Hamilton quaternions (sets of vectors involving imaginary numbers), are regularly used in today’s computer graphics and in the guidance systems of space craft; and Hamilton graphs are in common use in modern discrete mathematics. As well as studying mathematics, he also wrote poetry, and was a friend of William Wordsworth and Samuel Taylor Coleridge. Irish Universities Promoting Science William Rowan Hamilton (1805-1865)

7 离散数学 中国地质大学 计算机学院 7

8 8

9 9 11.1 哈密尔顿图 2002 年 “ 离散数学与计算机科 学研究中心 ” 在福州大学成立 范更华教授获 2005 年度国家 自然科学奖二等奖 —— 研究主题：哈密尔顿圈及 圈覆盖理论 ——“ 范定理 ” ( “ 范条件 ” 、 “ 范 类型 ”)

10 离散数学 中国地质大学 计算机学院 10 11.1 哈密尔顿图 范更华：歪打正著学了图论 灵光一闪发现定理 —— 科学中国人（ 2005 ）年度人物 哈密尔顿圈问题是图论最古老的研究课题之一，是至今未解决的世界难题，在许 多领域有着重要应用。经过多年艰苦攻克，范更华的这一项目在这一问题的研究 上开辟 了一条新的途径，证明若图中每对距离为 2 的点中有一点的度数至少是图 的点数的一半，则该图存在哈密尔顿圈。了此成果引发了大量后续工作，以 “ 范 定理 ” 、 “ 范 条件 ” 、 “ 范类型 ” 被广泛引用而出现于多种国际权威学术刊物，并作为 定理出现在国外的教科书中。 —— 新华网 2006.1.10

11 离散数学 中国地质大学 计算机学院 11 11.1 哈密尔顿图 哈密尔顿回路 (H- 回路 ): 一条经过图 G 中的每一个结点恰好一次的回路 ( 环 )  哈密尔顿图 (Hamilton Graph, H- 图 ): 具有哈密尔顿回路的图 哈密尔顿路 (H- 路 ): 一条经过图 G 中的每一个结点恰好一次的路 ( 通路 )  半哈密尔顿图

12 离散数学 中国地质大学 计算机学院 12 11.1 哈密尔顿图 示例 请判断下列各图中，哪些是哈密尔顿图？ （ a ） (b) (c) a b c d e

13 离散数学 中国地质大学 计算机学院 13 11.1 哈密尔顿图 哈密尔顿图性质 若图 G=(V ， E) 具有哈密尔顿回路，则对于结点集 V 的每一个非空子集 S 均有 ω(G － S)≤|S| 成立。其中 ω(G － S) 是 G － S 中连通分支数。 —— 哈密尔顿图的必要条件 —— 也是判定非哈密尔顿图的充分条件

14 离散数学 中国地质大学 计算机学院 14 11.1 哈密尔顿图 8×8 马图 ( 能否遍历  是否是 H 图 ?) 跳马的步数 1-64 ，构成一个幻 方

15 离散数学 中国地质大学 计算机学院 15 11.1 哈密尔顿图 4×4 马图 5×5 马图

16 离散数学 中国地质大学 计算机学院 16 11.2 哈密尔顿图判定定理 ( 充分条件 ) 设图 G 为具有 n(n≥3) 个结点的简单无向图， 1 如果 G 的每一对 ( 不相邻 ) 结点的度数之和都不小于 n–1 ，那么 G 中有一条 哈密尔顿通路； 2 如果 G 的每一对 ( 不相邻 ) 结点的度数之和不小于 n ，那么 G 为一哈密尔顿 图。 “ 范定理 ”: 若图中每对距离为 2 的结点中有一结点的度数至少是图的结点数的二分之 一，则该图存在哈密尔顿回路 ( 环 / 圈 ) 。

17 离散数学 中国地质大学 计算机学院 17 11.2 哈密尔顿图判定定理 判定定理 1 的证明 首先， G 是连通的 ? 若 G 有两个或更多互不连通的分图，设一个分图有 n 1 个结点，任取 一个结点 v 1 ，设另一个分图有 n 2 个结点，任取一个结点 v 2 ， 由 d(v 1 )≤n 1 － 1 ， d(v 2 )≤n 2 － 1 ， 有 d(v 1 )+ d(v 2 ) ≤n 1 + n 2 － 2 ＜ n － 1 ， 这表明与题设矛盾，故 G 必连通。

18 离散数学 中国地质大学 计算机学院 18 其次， G 有哈密尔顿通路？ 只要在 G 中构作出一条长为 n － 1 的 H- 通路即可得证。 为此，不妨令 P 为 G 中任意一条长为 p － 1(p ＜ n) 的 H- 通路，设其结 点序列为 v 1 ， v 2 ， … ， v p 。反复应用下面方法来扩充这一通路，直到 P 长度为 n-1 ： 1 ）如果有 v  v 1 ， v 2 ， … ， v p ，它与 v 1 或 v p 有边相关联，那么可 立即扩充 P 为长度为 p 的通路。 2 ）如果 v 1 ， v p 均只与原通路 P 上的结点相邻，则首先证明： G 中 有一条包含 v 1 ， v 2 ， … ， v p ，长度为 p 的回路。 2.1) 如果 v 1 与 v p 相邻，则回路已找到。否则 11.2 哈密尔顿图判定定理

19 离散数学 中国地质大学 计算机学院 19 11.2 哈密尔顿图判定定理 2.2 ) 如果 v 1 与 v i1,v i2, …,v ir 相邻， 1 ＜ i 1 ， i 2, …, i r ＜ p, 考虑 v p ： 若 v p 不与 v i1-1,v i2-1, …, v ir-1 中任何一个相邻，则 deg(v p )≤p-r-l ， 因而 deg(v 1 )+deg(v p )≤r+p–r–l=p–1 ＜ n–1 ，与题设矛盾， 因此 v p 与 v i1-1,v i2-1, …, v ir-1 之一, 例如 v i1-1 相邻， 于是, 可得到包含 v 1 ， v 2 ， … ， v p 的回路：（ v 1 ， v 2 ， … ， v i1-1,v p, v p -1, … ， v i1, v 1 ）如图所示。 v1v1 vpvp v2v2 v i-1 vivi

20 离散数学 中国地质大学 计算机学院 20 11.2 哈密尔顿图判定定理 考虑 G 中这条包含 v 1 ， v 2 ， … ， v p 、长度为 p 的回路。 由于 p<n ，故必有回路外结点 v 与回路上结点 ( 例如 v k ) 相邻，如图 所示，可以得到一条长度为 p 的、包含 v 1 ， v 2 ， … ， v p 的通路： (v, v k,v k-1,…, v 1,v i1,v i1+1,…, v p,v i1-1,…, v k+1 ) 。 v1v1 vpvp v2v2 vkvk v k+1 v v i-1 vivi

21 离散数学 中国地质大学 计算机学院 21 11.2 哈密尔顿图判定定理 请你思考 如何证明判定定理 2 ？ 1 按照上述证明方法？ 2 其它方法，如教材方法 (p224) ？ 构造法反证法

22 离散数学 中国地质大学 计算机学院 22 11.2 哈密尔顿图判定定理 练习 1 结点数目不少于 3 的完全图都是哈密尔顿图？ 2 哈密尔顿图中的哈密尔顿回路未必是唯一的吗？ 3 每个结点度数均不小于 n/2 的图是哈密尔顿图（ n 为图的结点数）？ 4 前述判定定理给出的条件只是充分条件，不是必要条件。请举例说明 之。 5 设 G 为（ n ， m ）图。请证明：如果 ，那么 G 为哈密尔顿图。

23 离散数学 中国地质大学 计算机学院 23 小结与作业 小结 1 哈密尔顿图 2 哈密尔顿图的判定 作业 习题 28 、 29 反证法反证法 构造法构造法