离散数学─图论 南京大学计算机科学与技术系

Presentation on theme: "离散数学─图论 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─图论 南京大学计算机科学与技术系
哈密尔顿图 离散数学─图论 南京大学计算机科学与技术系

2 内容提要 哈密尔顿通路 哈密尔顿回路 哈密尔顿图的必要条件 哈密尔顿图的充分条件 哈密尔顿图的应用 竞赛图与有向哈密尔顿通路

3 周游世界的游戏 沿着正十二面体的棱寻找一条旅行路线, 通过每个顶点恰好一次又回到出发点. (Hamilton 1857)

4 Hamilton通路/回路 G中Hamilton通路 G中Hamilton回路 Hamilton回路与 Hamilton通路
通路上各顶点不重复 G中Hamilton回路 除了起点与终点相同之外，通路上各顶点不重复。 Hamilton回路与 Hamilton通路 Hamilton通路问题可转化为Hamilton回路问题 G*K1 和Euler路不同，Hamilton路感兴趣的是图中的点，一条Hamilton路决不会在两点间走两次以上，因此，没有必要在有向图中讨论它，只要在图中讨论它就可以了。 一个邮递员，如果他的任务需要遍历某些特定的街道，那么他最好走一条Euler路；如果他的任务是联系某些特定的收发点，那么他最好走一条Hamilton路。 Euler路同Hamilton路相比较，前者要周游诸弧，后者要周游诸点，虽然仅有一字之差，但两者的困难程度却不大相同。对于前者，在上节我们已经得到了一些较为深刻的定理，比较满意地解决了这个问题；但对于后者，却没有令人满意的结果。寻找一个图是Hamilton图的充分必要条件，仍是图论中一个重要问题。

5 Hamilton回路的基本特性 Hamilton回路:无重复地遍历图中诸点, Euler回路:无重复地遍历图中诸边.
若图G中有一顶点的度为1, 则无Hamilton回路. 设图G中有一顶点的度大于2, 若有Hamilton回路, 则只用其中的两条边. 若图中有n个顶点, 则Hamilton回路恰有n条边. 注：Hamilton回路问题主要针对简单图。

6 Hamilton回路的存在性问题 K3 K4 Kn(n3)有Hamilton回路 a c b e d

7 一个基本的必要条件 如果图G=(V, E)是Hamilton图，则对V的任一非空子集S，都有 P(G-S) |S|
其中， P(G-S)表示图G-S的连通分支数. 理由：设C是G中的Hamilton回路, P(G-S) P(C-S) |S| 向一个图中顶点之间加边不会增加连通分支。

8 必要条件的应用

9 举例 b a c 将图中点a, b, c的集合记为S, G-S有4个连通分支,而|S|=3. G不是Hamilton图.

10 举例 Kh Kh Kn-2h 下图给出的是 C2,7的具体图 (h=2,n=7)

11 必要条件的局限性 必要条件只能判定一个图不是哈密尔顿图 Petersen图满足上述必要条件，但不是哈密尔顿图。
P当且仅当Q：P，当Q ===== Q=》P； P，仅当Q ===== P=》Q。 必要性证明就是证明P=》Q，证明Q是P的必要条件。

12 哈密尔顿图的充分条件 Dirac定理（狄拉克, 1952）
设G是无向简单图，|G|=n3 ， 若 (G) n/2，则G有哈密尔顿回图. Ore定理（奥尔, 1960） 设G是无向简单图，|G|=n3 ，若G中任意不相邻的顶点对u,v均满足： d(u)+d(v)n ，则G有哈密尔顿回图。 设G是无向简单图, |G|=n2, 若G中任意不相邻的顶点对u,v均满足：d(u)+d(v)n-1，则G是连通图。 假设G不连通，则至少含2个连通分支，设为G1, G2。取xVG1, yVG2, 则：d(x)+d(y)(n1-1)+(n2-1)n-2 (其中ni是Gi的顶点个数)，矛盾。

13 充分条件的讨论 “ (G) n/2”不能减弱为：  (G) 举例，n=5， (G)=2 . G不是Hamilton图.
存在哈密尔顿通路的充分条件（Ore定理的推论） 设G是无向简单图，|G|=n2 ，若G中任意不相邻的顶点对u,v均满足： d(u)+d(v)n-1 ，则G有哈密尔顿通路。

14 Ore定理的证明 Ore定理（1960） 设G是无向简单图，|G|=n3，若
对G中任意不相邻的顶点u和v, d(u)+d(v)n （*） 则G有哈密尔顿回图。 证明.反证法, 若存在满足（*）的图G，但是G没有Hamilton回路. 不妨假设G是边极大的非Hamilton图，且满足（*）。若G不是边极大的非Hamilton图，则可以不断地向G增加若干条边,把G变成边极大的非Hamilton图G’，G’依然满足（*），因为对vV(G), dG(v)dG’(v)。

15 Ore定理的证明 设u, v是G中不相邻的两点，于是G+uv是Hamilton图，且其中每条Hamilton回路都要通过边uv. 因此，G中有起点为u，终点为v的Hamilton通路: u=v1 vi-1 vi v=vn 不存在两个相邻的顶点 vi-1和vi,使得vi-1与v相邻且vi 与u相邻. 若不然, (v1,v2, … vi-1, vn, …, vi, v1)是G的Hamilton回路. 设在G中u与vi1, vi2, …, vik相邻, 则v与vi1-1, vi2-1, …vik-1都不相邻, 因此d(u)+d(v) k+[(n-1)-k]<n. 矛盾.

16 Ore定理的延伸 引理. 设G是有限图，u, v是G中不相邻的两个顶点，并且满足：d(u)+d(v)  |G|，则
G是Hamilton图  G∪{uv}是Hamilton图. 证明：类似于Ore定理的证明. G的闭合图, 记为C(G): 连接G中不相邻的并且其度之和不小于 |G| 的点对, 直到没有这样的点对为止. 有限图G是Hamilton图充分必要其闭合图C(G)是Hamilton图.

17 闭合图(举例) a f e d c b

18 判定定理的盲区 从“常识”出发个案处理 一顶点关联的边中恰有两 条边在哈密尔顿回路中。 哈密尔顿回路中不能含 真子回路。 利用对称性
利用二部图特性 …

19 判定哈密尔顿图的例子 下列图中只有右图是哈密尔顿图。

20 棋盘上的哈密尔顿回路问题 在44或55的缩小了的国际象棋棋盘上，马(Knight)不可能从某一格开始，跳过每个格子一次，并返回起点。
灰（13个） VS 白（12个）

21 哈密尔顿图问题 基本问题 判定哈密尔顿回路的存在性 找出哈密尔顿回路/通路 （在最坏情况下）时间复杂性为多项式的算法？

22 应用（格雷码） 给定一个立方体图，求出哈密尔顿回路 Q3 100 101 000 001 110 111 010 011

23 安排考试日程（哈密尔顿通路） 问题: 在6天里安排6门课 – A,B,C,D,E,F -的考试，每天考1门。假设每人选修课的情况有如下的4类：DCA，BCF，EB，AB。如何安排日程，使得没有人必须连续两天有考试？ A B A B F F C C E D E D

24 竞赛图 底图为K4的竞赛图： A B C 以上每个图可以看作4个选手参加的循环赛的一种结果

25 竞赛图与有向哈密尔顿通路 底图是完全图的有向图称为竞赛图。 利用归纳法可以证明竞赛图含有向哈密尔顿通路。

26 作业 教材[9.5] (p.497) 40, 41, 42 45, 46, 49, 63 补充 考虑在7天安排7门课程的考试，使得同一位老师所任的两门课程考试不排在接连的两天中，试证明如果没有老师担任多于4门课程，则符合上述要求的考试安排总是可能的.

27 循环赛该如何排名次 按照在一条有向Hamilton通路(一定存在)上的顺序排名： C A B D E F
A B D E F C C 从第一名变成了最后一名 E D

28 循环赛该如何排名次 按照得胜的竞赛场次(得分)排名： A(胜4) B,C(胜3) D, E(胜2) F(胜1)
问题：很难说B,C并列第二名是否公平，毕竟C战胜的对手比B战胜的对手的总得分更高(9比5)。 E D

29 循环赛该如何排名次 当问题竞赛图是强连通且至少有4个选手时，这个序列一定收敛于一个固定的排列，这可以作为排名：A C B E D F。
建立对应与每个对手得分的向量 s1 = (a1, b2, c3, d4, e5, f6) 然后逐次求第k级的得分向量sk, 每个选手的第k级得分是其战胜的对手在第k-1级得分的总和。 A B F C 对应于左图所示的竞赛结果，得分向量： s1=(4,3,3,2,2,1) s2=(8,5,9,3,4,3) s3=(15,10,16,7,12,9) s4=(38,28,32,21,25,16) s5=(90,62,87,41,48,32) E D 当问题竞赛图是强连通且至少有4个选手时，这个序列一定收敛于一个固定的排列，这可以作为排名：A C B E D F。