欧拉图与汉密尔顿图.

Presentation on theme: "欧拉图与汉密尔顿图."— Presentation transcript:

1 欧拉图与汉密尔顿图

2 回顾 通路与回路 无向图的连通性 连通度 2-连通图 有向图的连通性 无向图的定向

3 提要 欧拉通路/回路 欧拉图的充要条件 构造欧拉回路的Fleury算法 哈密尔顿通路/回路 哈密尔顿图的必要和充分条件 哈密尔顿图的应用

4 回顾 邮递员从邮局出发，走过辖区内每条街道至少一次， 再回邮局，如何选择最短路线？
n个城市间均有道路，但距离不等，旅行商从某地出 发，走过其它n-1个城市，且只经过一次，最后回到 原地，如何选择最短路线？

5 Königsberg七桥问题（回顾） 问题的抽象： 用顶点表示对象-“地块” 用边表示对象之间的关系-“有桥相连”
原问题等价于：“右边的图中是否存在包含每条边一次且恰好一次的回路？” C D A B A D C B

6 “一笔划”问题 ？

7 欧拉通路和欧拉回路 定义：包含图（无向图或有向图）中每条边的简单通路称为欧拉通路。 定义：包含图中每条边的简单回路称为欧拉回路。
注意：欧拉通路是简单通路（边不重复），但顶点可重复 定义：包含图中每条边的简单回路称为欧拉回路。 如果图G中含欧拉回路，则G称为欧拉图。如果图G中有欧拉通路，但没有欧拉回路，则G称为半欧拉图。 //备注：通常假设G是连通的。

8 欧拉图的充要条件 连通图G是欧拉图 当且仅当 G中每个顶点的度数均为偶数。 证明：
设C是G中的欧拉回路，则vVG, d(v)必等于v在C上出现数的2倍(起点与终点看成出现一次)。 可以证明： （1）G中所有的边可以分为若干边不相交的初级回路。 （2）这些回路可以串成一个欧拉回路。

9 欧拉图的充要条件 (1) 若图G中任一顶点均为偶度点，则G中所有的边包含在若干边不相交的简单回路中。 证明：对G的边数m施归纳法。
当m=1, G是环，结论成立。 对于k1，假设当mk时结论成立。 考虑m=k+1的情况：注意G2, G中必含简单回路，记为C，令G’=G-EC, 设G’中含s个连通分支，显然，每个连通分支内各点均为偶数(包括0)，且边数不大于k。则根据归纳假设，每个非平凡的连通分支中所有边含于没有公共边的简单回路中，注意各连通分支以及C两两均无公共边，于是，结论成立。

10 欧拉图的充要条件 (2) 若连通图G中所有的边包含在若干边不相交的简单回路中， 则G中含欧拉回路。
证明：对G中简单回路个数d施归纳法。当d=1时显然。 假设dk(k1)时结论成立。考虑d=k+1. 按某种方式对k+1个简单回路排序，令G’=G-E(Ck+1)，设G’中含s个连通分支，则每个非平凡分支所有的边包含在相互没有公共边的简单回路中，且回路个数不大于k。由归纳假设，每个非平凡连通分支Gi均为欧拉图，设其欧拉回路是Ci'。因G连通，故Ck+1与诸Ci’都有公共点。 G中的欧拉回路构造如下：从Ck+1上任一点(设为v0)出发遍历Ck+1上的边，每当遇到一个尚未遍历的Ci'与Ck+1的交点(设为vi'), 则转而遍历Ci'上的边，回到vi'继续沿Ck+1进行。

11 关于欧拉图的等价命题 设G是非平凡连通图，以下三个命题等价： (1) G是欧拉图。 (2) G中每个顶点的度数均为偶数。

12 半欧拉图的判定 设G是连通图，G是半欧拉图 当且仅当 G恰有两个奇度点。 证明:
 设P是G中的欧拉通路(非回路)，设P的始点与终点分别 是u,v, 则对G中任何一点x, 若x非u,v，则x的度数等于 在P中出现次数的2倍，而u,v的度数则是它们分别在P 中间位置出现的次数的两倍再加1。  设G中两个奇度顶点是u,v, 则G+uv是欧拉图，设欧拉 回路是C, 则C中含uv边，C-uv是G中的欧拉通路。 (这表明：如果试图一笔画出一个半欧拉图，必须以两 个奇度顶点为始点和终点。)

13 构造欧拉回路 思想：在画欧拉回路时，已经经过的边不能再用。因此， 在构造欧拉回路过程中的任何时刻，假设将已经经过的边 删除，剩下的边必须仍在同一连通分支当中。

14 构造欧拉回路-Fleury算法 算法： 输入：欧拉图G
输出：简单通路P = v0e1v1e2,…,eiviei+1,…,emvm, 其中包含了EG中所有的元素。 1. 任取v0VG, 令P0=v0; 2. 设Pi=v0e1v1e2,…,eivi, 按下列原则从EG-{e1,e2,…,ei}中选择ei+1。 (a) ei+1与vi相关联； (b) 除非别无选择，否则ei+1不应是G-{e1,e2,…,ei}中的割边。 3. 反复执行第2步，直到无法执行时终止。

15 Fleury算法的证明 算法的终止性显然。 设算法终止时，Pm= v0e1v1e2,…,eiviei+1,…,emvm,
(1) Pm是回路，即v0=vm。 (2) Pm包括了G中所有的边。 令Gi=G-{e1,e2,…,ei} (1) (证明是回路)假设v0vm。由算法终止条件，在Gm中已 没有边与vm相关联。假设除最后一次外，vm在Pm中出现 k次，则vm的度数是2k+1, 与G中顶点度数是偶数矛盾。

16 Fleury算法的证明 (2) (证明含所有边)假设Pm没有包括G中所有的边，令Gm中所 有非零度顶点集合为S（非空）, 令S' =VG-S, 则vmS'。 考察序列e1,e2,…ej,ej+1,…,em。假设j是满足vjS, 而vj+1S’的最大下标。 如果没有这样的j，G就不连通，矛盾。因为Pm的终点在S’中，因此ej+1 一定是Gj中的割边。 令e是在Gj中与vj相关联的异于ej+1的边(非零度点一定有), 根据算法选择 ej+1(割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是Gj的割边。矛盾。 没包括所有边一定是因为之前路过一个割边（且割边之前那个联通分支还没走完） v e vj vj+1 ej+1 vm S’ S

17 有向欧拉图 有向图中含所有边的有向简单回路称为有向欧拉回路。 含有向欧拉回路的有向图称为有向欧拉图。
下面的等价命题可以用于有向欧拉图的判定： 若G是弱连通的有向图，则下列命题等价： G中含有向欧拉回路。 G中任一顶点的入度等于出度。 G中所有的边位于若干个边互不相交的有向简单回路当中。 (证明与无向欧拉图类似。)

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

19 Hamilton通路/回路 G中Hamilton通路 G中Hamilton回路 Hamilton回路与 Hamilton通路
通路上各顶点不重复 G中Hamilton回路 除了起点与终点相同之外，通路上各顶点不重复。 Hamilton回路与 Hamilton通路 Hamilton通路问题可转化为Hamilton回路问题 和Euler路不同，Hamilton路感兴趣的是图中的点，一条Hamilton路决不会在两点间走两次以上，因此，没有必要在有向图中讨论它，只要在图中讨论它就可以了。 Euler路同Hamilton路相比较，前者要周游诸弧，后者要周游诸点，虽然仅有一字之差，但两者的困难程度却不大相同。对于前者，在上节我们已经得到了一些定理，比较满意地解决了这个问题；但对于后者，却没有令人满意的结果。寻找一个图是Hamilton图的充分必要条件，仍是图论中一个重要问题。

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

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

22 哈密尔顿图的必要条件 如果图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| 向一个图中顶点之间加边不会增加连通分支。

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

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

25 例

26 必要条件的局限性 必要条件只能判定一个图不是哈密尔顿图 Petersen图满足上述必要条件，但不是哈密尔顿图。

27 哈密尔顿图的充分条件 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的顶点个数)，矛盾。

28 充分条件的讨论 “ (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有哈密尔顿通路。

29 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)。

30 Ore定理的证明 设u, v是G中不相邻的两点，于是G+uv是Hamilton图. 因此，G中有起点为u，终点为v的Hamilton通路:
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. 矛盾. 有个-1是自己到自己的连接

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

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

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

34 判定哈密尔顿图的例子 下列图中只有右图是哈密尔顿图。 左：考虑外围三点，其两边必须都在哈密尔顿回路上，中间一点就三次了；
中：二部图；7个红点；9个黄点

35 棋盘上的哈密尔顿回路问题 在44或55的缩小了的国际象棋棋盘上，马 (Knight)不可能从某一格开始，跳过每个格子一次， 并返回起点。
二部图；25步骤 最后是白色； 必要条件，删中间两点，三个连通分支

36 Knight's tour From wikipedia

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

38 应用（格雷码） 给定一个立方体图，求出哈密尔顿回路 Q3 100 101 000 001 110 111 010 011
A Gray code is a labeling of the arcs of the circle such that adjacent arcs are labeled with bit strings that differ in exactly one bit. The assignment in Figure 12(b) is a Gray code. We can find a Gray code by listing all bit strings of length n in such a way that each string differs in exactly one position from the preceding bit string, and the last string differs from the first in exactly one position. We can model this problem using the n-cube Qn. 按自然数递增计数，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生 指针误差一点点可导致3位都错了

39 安排考试日程 问题: 在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

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

41 竞赛图与有向哈密尔顿通路 底图是完全图的有向图称为竞赛图。 利用归纳法可以证明竞赛图含有向哈密尔顿通路。
对n作归纳法。n=2时，D的底图为K2，结论成立。 设n=k时结论成立。 现在设n=k+1.设V(D)={v1,v2,…,vk,vk+1}。令D1=D-vk+1，易知D1为k阶竞赛图，由归纳假设可知，D1存在哈密顿通路，设Г1=v‘1v’2…v‘k为其中一条。下面证明vk+1可扩到Г1中去。若存在v’r（1≤r≤k），有<v‘i,vk+1>∈E(D)，i=1,2,…,r-1，而<vk+1,v’r>∈E(D)，见左图所示，则Г=v‘1v’2…v‘r-1vk+1v’r…v‘k为D中哈密顿通路。否则，i∈{1,2,…,k}，均有<v’i,vk+1>∈E(D)，见右图所示，则Г=Г'∪<v'k,vk+1>为D中哈密顿通路。

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

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

44 循环赛该如何排名次 当问题竞赛图是强连通且至少有4个选手时，这个序列一定收敛于一个固定的排列，这可以作为排名：A C B E D F。
建立对应与每个对手得分的向量 s1 = (a1, b2, c3, d4, e5, f6) 然后逐次求第k级的得分向量sk, 每个选手的第k级得分是其战胜的对手在第k-1级得分的总和。 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。

45 作业 见课程网站

46 中国邮递员问题（管梅谷，1962） 问题：邮递员从邮局出发，走过辖区内每条街道至少一 次，再回邮局，如何选择最短路线？ 数学模型
无向带权图G: EG中元素对应于辖区内的街道，VG中的元 素对应于街道的交叉点，街道长度用相应边的权表示。 问题的解: G中包含所有边的权最小的回路，称为最优回路 (注意：未必是简单回路)。 当G是欧拉图，则最优回路即欧拉回路。 若G不是欧拉图，则通过加边来消除G中的奇度顶点，要求 使加边得到的欧拉图G*中重复边的权和最小。

47 中国邮递员问题 通过加边来消除G中的奇度顶点，使得加边得到的欧拉图 G*中重复边的权和最小。

48 中国邮递员问题-求解原理 C是带正权无向连通图G中的最优回路 当且仅当 对应的欧拉 图G*满足： (1) G的每条边在G*中至多重复一次；
(2) 若G中的回路C1在G*中重复边的权和大于C1的权的一半， 按如下方式改造G*: C1上原有的重复边均删除，而原来未重复的边 均添加重复边，设得到的图为G"。显然，G"中每个顶点的度数仍 是偶数，但G"中重复边的权和小于G*中相应的值，矛盾。

49 中国邮递员问题-求解原理（续）  只需证明：满足上述两个条件的回路的权均相等。
假设C1和C2是满足上述条件的两个回路，相应的欧拉图是 G1*和G2*，添加的重复边集合分别是F1和F2。令F= F1F2, G[F]是F生成的导出子图。注意：构造G1*和G2*时，在G 的任意顶点上添加的边数同奇偶性(与该点在G中度数同奇 偶性)，因此G[F]中各顶点度数均为偶数，G[F]是若干边 不重复的初级回路的并集。 考虑G[F]的任一回路C', C'上属于F1的边的权和与属于F2的 边的权和都不能超过C'的权的一半，因此必然相等。由此 易知，构造G1*和G2*时添加的边的权和必然相等。于是 G1*和G2*的权相等，即C1和C2的权相等。

50 中国邮递员问题-算法 算法过程 1．用Dijkstra算法求所有奇度顶点对之间的最短路径。 (若G是欧拉图，直接用Fleury算法)
2．以G中所有奇度顶点构造带权完全图G2k, 每边的权是 两顶点间最短路径长度。 3．求G2k中的最小权完美匹配M。 4．按照M中的各个路径添加重复边。 再用Fleury算法求 欧拉回路。

51 随机欧拉图 设G是欧拉图，vVG，从v开始，每一步从当前点所关联边中随机选边，均可构造欧拉回路，则G称为以v为始点的随机欧拉图。
的随机欧拉图，则一定存在已经包含 了v所关联的所有边，却未包含G中所 有边的简单回路。

52 随机欧拉图的判定 欧拉图G是以v为始点的随机欧拉图当且仅当 G中任一回路均 包含v。
 若G是以v为始点的随机欧拉图，假设有回路C不包含v. 令 G'=G-C, (G'可能不连通)，G'中包含v的那个连通分支一定 是欧拉图，相应的欧拉回路包含了v关联的所有边，但不包 含G中的所有边，与G是以v为始点的随机欧拉图矛盾。  若欧拉图G中任意回路均包含v。假设G不是以v为始点的 随机欧拉图，则一定存在已经包含了v所关联的所有边，却 未包含G中所有边的简单回路C，假设e是不在C中的一条 边，e的端点必异于v，设一个是u。令从G中删除C中所有 边的图为G'，显然在G'中v是孤立点。而包含u的连通分支 是欧拉图，因此u必包含在一回路中，但此回路不含v，矛 盾。 (易推知：欧拉图G是以任一顶点为始点的随机欧拉图 当且仅当 G本身是一个初级回路)