离散数学第十五章.ppt

第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图主要内容主要内容l带权图与货郎担问题带权图与货郎担问题1第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图预备知识预备知识l无向图无向图G = ld(v), d+(v), d (v)l奇度顶点与偶度顶点奇度顶点与偶度顶点l连通，通路，回路连通，通路，回路2•瑞士数学家，最多产的数学家–≥ 1100书籍论文–全集≥75卷–13个孩子–最后17年失明 ADBCQuestion:•如何将左边图所示的七桥问题转换为点和边来描述?•一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？ Link to the videoLeonhard Euler:1707~1783历史背景历史背景3下面哪些图形可以一笔画，哪些图形不能一笔画？下面哪些图形可以一笔画，哪些图形不能一笔画？试一试：试一试：(1)(2)(3)(4)(5)(6)4（（2））（（2））（（2））（（2））（（3））（（3））（（4））（（4））（（2））（（2））（（3））（（2））（（3））（（2））（（3））（（4））（（3））（（1））（（1））（（1））（（3））（（4））（（2））（（2））（（2））偶点偶点（（1））（（3））（（2））（（2））奇点奇点5●中途点特征：中途点特征：笔沿着某条边进去后，必定沿另笔沿着某条边进去后，必定沿另一条边出去，于是知道与中途点一条边出去，于是知道与中途点为端点的边必定是成对出现的，为端点的边必定是成对出现的，这样中途点必定是偶点。

这样中途点必定是偶点进去进去出来出来进去进去出来出来p如果起点和终点重合，则与他们相连的边是偶数条，所以如果起点和终点重合，则与他们相连的边是偶数条，所以也是偶点也是偶点p起点和终点不重合，与他们相连的边奇数条，则是都是奇起点和终点不重合，与他们相连的边奇数条，则是都是奇点点“一笔画一笔画”图形特征：一个图形可以图形特征：一个图形可以“一笔画一笔画”则奇则奇点的个数是点的个数是0个或个或2个个6欧拉图定义欧拉图定义定义定义15.1 (1) 欧拉通路欧拉通路——经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的通路点的通路. (2) 欧拉回欧拉回路路——经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的回路点的回路.(3) 欧拉图欧拉图——具有欧拉回路的图具有欧拉回路的图.(4) 半欧拉图半欧拉图——具有欧拉通路而无欧拉回路的图具有欧拉通路而无欧拉回路的图.几点说明：几点说明：规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性环不影响图的欧拉性.7上图中，上图中，(1) ,(4) 为欧拉图，为欧拉图，(2),(5)为半欧拉图，为半欧拉图，(3),(6)既不是既不是欧拉图，也不是半欧拉图欧拉图，也不是半欧拉图. 在在(3),(6)中各至少加几条边才能成中各至少加几条边才能成为欧拉图？为欧拉图？ 欧拉图实例欧拉图实例8无向欧拉图的判别法无向欧拉图的判别法定理定理15.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G连通且无奇度数顶点连通且无奇度数顶点.证证 若若G 为平凡图无问题为平凡图无问题. 下设下设G为为 n 阶阶 m 条边的无向图条边的无向图.必要性必要性 设设C 为为G 中一条欧拉回路中一条欧拉回路.(1) G 连通显然连通显然.(2)  vi V(G)，，vi在在C上每出现一次获上每出现一次获2度，所以度，所以vi为偶度顶点为偶度顶点. 由由vi 的任意性，结论为真的任意性，结论为真. 充分性充分性 对边数对边数m做归纳法（第二数学归纳法）做归纳法（第二数学归纳法）.(1) m=1时，时，G为一个环，则为一个环，则G为欧拉图为欧拉图.(2) 设设m k（（k 1）时结论为真，）时结论为真，m=k+1时如下证明：时如下证明：9PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图并，见示意图3. 10欧拉图的判别法欧拉图的判别法定理定理15.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G 连通且恰有两个奇连通且恰有两个奇度顶点度顶点.证证 必要性简单必要性简单. 充分性（利用定理充分性（利用定理15.1））设设u,v为为G 中的两个奇度顶点，令中的两个奇度顶点，令 G   =G (u,v)则则G   连通且无奇度顶点，由定理连通且无奇度顶点，由定理15.1知知G  为欧拉图，因而为欧拉图，因而存在欧拉回路存在欧拉回路C，令，令  =C (u,v)则则  为为 G 中欧拉通路中欧拉通路.11下图是某展览厅的平面图，它由五个展室组成，任两展室之下图是某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个出口，问间都有门相通，整个展览厅还有一个进口和一个出口，问游人能否一次不重复地穿过所有的门，并且从入口进，从游人能否一次不重复地穿过所有的门，并且从入口进，从出口出？出口出？AFDCBE练习练习 112下图是一个公园的平面图下图是一个公园的平面图. .要使游客走遍每条路而不重复，要使游客走遍每条路而不重复，问出入口应设在哪里？问出入口应设在哪里？ABCC DEFGHIJK练习练习 213有向欧拉图的判别法有向欧拉图的判别法定理定理15.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶是强连通的且每个顶点的入度都等于出度点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1. 定理定理15.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大中恰有两个奇度顶点，其中一个的入度比出度大1，另一个，另一个的出度比入度大的出度比入度大1，而其余顶点的入度都等于出度，而其余顶点的入度都等于出度. 本定理的证明类似于定理本定理的证明类似于定理15.1. 定理定理15.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干是连通的且为若干个边不重的圈之并个边不重的圈之并. 可用归纳法证定理可用归纳法证定理15.5. 141.1.查阅有关欧拉图应用研究的文献查阅有关欧拉图应用研究的文献2.2.书面总结书面总结: : –研究动机研究动机–研究框架研究框架–关键的发现关键的发现–结论结论作业作业1515.2 哈密顿图哈密顿图历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图 (1) (2) 1617哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义15.2 (1) 哈密顿通路哈密顿通路——经过图中所有顶点一次仅一次的通路经过图中所有顶点一次仅一次的通路.(2) 哈密顿回路哈密顿回路——经过图中所有顶点一次仅一次的回路经过图中所有顶点一次仅一次的回路.(3) 哈密顿图哈密顿图——具有哈密顿回路的图具有哈密顿回路的图.(4) 半哈密顿图半哈密顿图——具有哈密顿通路且无哈密顿回路的图具有哈密顿通路且无哈密顿回路的图.几点说明：几点说明：平凡图是哈密顿图平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上哈密顿图的实质是能将图中的所有顶点排在同一个圈上18实例实例在上图中，在上图中，(1),(2) 是哈密顿图是哈密顿图;(3)是半哈密顿图是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？既不是哈密顿图，也不是半哈密顿图，为什么？19无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件定理定理15.6 设无向图设无向图G=是哈密顿图，对于任意是哈密顿图，对于任意V1 V且且V1，均有，均有 p(G V1)   |V1|证证 设设C为为G中一条哈密顿回路中一条哈密顿回路(1) p(C V1)   |V1|(2) p(G V1)   p(C V1)   |V1| （因为（因为C G））推论推论 设无向图设无向图G=是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 V且且V1均有均有 p(G V1)   |V1|+1证证 令令  uv为为G中哈密顿通路，令中哈密顿通路，令G  = G (u,v)，则，则G 为为哈密顿图哈密顿图. 于是于是 p(G V1) = p(G V1 (u,v))   |V1|+120(1)(1)若若G G是哈密顿图，则一定满足上式；是哈密顿图，则一定满足上式；(2)(2)满足上式却不一定是哈密顿图；满足上式却不一定是哈密顿图；(3)(3)不满足上式一定不是哈密顿图。

不满足上式一定不是哈密顿图21定理应用举例利用定理说明下图不是哈密顿图22解答取取S={vS={v1 1,v,v4 4} }，则：，则：|S|=2p(V-S)=3，， 不满足：不满足： p(V-S)≤|S|不是哈密顿图不是哈密顿图23几点说明几点说明l由定理由定理15.6立刻可知，立刻可知，Kr,s当当s r+1时不是哈密顿图时不是哈密顿图. 易知易知Kr,r（（r 2）时都是哈密顿图，）时都是哈密顿图，Kr,r+1都是半哈密顿图都是半哈密顿图. l常利用定理常利用定理15.6判断某些图不是哈密顿图判断某些图不是哈密顿图.例例2 设设G为为n阶无向连通简单图，若阶无向连通简单图，若G中有割点或桥，则中有割点或桥，则G不不 是哈密顿图是哈密顿图.证证 设设v为割点，则为割点，则 p(G v)   2>|{v}|=1. K2有桥，它显然不是哈密顿图有桥，它显然不是哈密顿图. 除除K2外，其他有桥的图外，其他有桥的图（连通的）均有割点（连通的）均有割点.其实，本例对非简单连通图也对其实，本例对非简单连通图也对.24无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件定理定理15.7 设设G是是n阶无向简单图，若对于任意不相邻的顶点阶无向简单图，若对于任意不相邻的顶点vi,vj，均有，均有 d(vi)+d(vj)   n 1 ( )则则G 中存在哈密顿通路中存在哈密顿通路. 推论推论 设设G为为n (n 3) 阶无向简单图，若对于阶无向简单图，若对于G中任意两个中任意两个不相邻的顶点不相邻的顶点vi,vj，均有，均有 d(vi)+d(vj)   n （（））则则G中存在哈密顿回路，从而中存在哈密顿回路，从而G为哈密顿图为哈密顿图.25几点说明几点说明由定理由定理15.7的推论可知，的推论可知，Kn（（n 3）均）均为哈密顿图为哈密顿图.(1)(1)满足上式一定是哈密顿图；满足上式一定是哈密顿图；(2)(2)是哈密顿图不一定满足上式；是哈密顿图不一定满足上式；(3)(3)不是哈密顿图一定不满足上式。

不是哈密顿图一定不满足上式完全图完全图Kn (n 3) 中任何两个顶点中任何两个顶点u,v，均有，均有 d(u)+d(v) = 2(n 1)   n（（n 3），），所以所以Kn为哈密顿图为哈密顿图. 26定理应用举例任意两点的度之和为任意两点的度之和为4 4n=6n=6不满足不满足d(vi)+d(vj) ≥ n但却是哈密顿图，但却是哈密顿图，也有哈密顿路径也有哈密顿路径是哈密顿图是哈密顿图27n（（n 2）阶竞赛图中存在哈密顿通路）阶竞赛图中存在哈密顿通路定理定理15.9 若若D为为n（（n 2）阶竞赛图，则）阶竞赛图，则D中具有哈密顿通路中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图证明思路：注意，竞赛图的基图是无向完全图. 对对n（（n 2））做归纳做归纳. 只需观察下面两个图只需观察下面两个图. 无向哈密顿图的充分条件无向哈密顿图的充分条件28设设GG，，称称 为为G 的权，并记作的权，并记作W(G )，即，即定定义15.3 给定定图G = ，，(G为无向无向图或有向或有向图)，，设W:ER (R为实数集数集)，，对G中任意中任意边e = (vi,vj) (G为有向图为有向图时，时，e = )，设，设W(e) = wij，称实数，称实数wij 为边为边e上的上的权权，并将，并将wij标注在边标注在边e上，称上，称G为为带权图带权图，此时常将带权图，此时常将带权图G记作记作 . 15.3 最短路问题最短路问题与货郎担问题与货郎担问题29例：一位旅客要从例：一位旅客要从A城到城到B城城他希望选择一条途中中转次数最少的路线；他希望选择一条途中中转次数最少的路线；他希望选择一条途中所花时间最短的路线；他希望选择一条途中所花时间最短的路线；他希望选择一条途中费用最小的路线；他希望选择一条途中费用最小的路线；v5v4v3v2v1v0 100 6030101020 5 50这些问题均是带权图上的最短路径问题。

这些问题均是带权图上的最短路径问题1.边上的权表示一站边上的权表示一站2.边上的权代表距离边上的权代表距离3.边的权代表费用边的权代表费用 30货郎担问题货郎担问题设设G=为一个为一个n阶完全带权图阶完全带权图Kn，各边的权非负，且，各边的权非负，且有的边的权可能为有的边的权可能为 . 求求G中的一条最短的哈密顿回路，这就中的一条最短的哈密顿回路，这就是货郎担问题的数学模型是货郎担问题的数学模型. 完全带权图完全带权图Kn（（n 3）中不同的哈密顿回路数）中不同的哈密顿回路数(1) Kn中有中有(n 1)! 条不同的哈密顿回路（定义意义下）条不同的哈密顿回路（定义意义下）(2) 完全带权图中有完全带权图中有(n 1)! 条不同的哈密顿回路条不同的哈密顿回路(3) 用穷举法解货郎担问题算法的复杂度为用穷举法解货郎担问题算法的复杂度为(n 1)！，当！，当n较较大时，计算量惊人地大大时，计算量惊人地大31 解解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9可见可见C3 (见图中见图中(2)) 是最短的，其权为是最短的，其权为9. 例例6 求图中求图中(1) 所示带权图所示带权图K4中最短哈密顿回路中最短哈密顿回路. (1) (2) 321. 设设G为为n（（n 2）阶无向欧拉图，证明）阶无向欧拉图，证明G中无桥中无桥(见例见例1思考题思考题)方法二：反证法方法二：反证法. 利用欧拉图无奇度顶点及握手定理的推论利用欧拉图无奇度顶点及握手定理的推论. 否则，设否则，设e=(u,v)为为G中桥，则中桥，则G e产生两个连通分支产生两个连通分支G1, G2，不妨设，不妨设u在在G1中，中，v在在G2中中. 由于从由于从G中删除中删除e时，只改变时，只改变u,v 的度数的度数(各减各减1)，因而，因而G1与与G2中均只含一个奇度顶点，这与握中均只含一个奇度顶点，这与握手定理推论矛盾手定理推论矛盾.练习练习1方法一：直接证明法方法一：直接证明法. 命题命题 (*)：设：设C为任意简单回路，为任意简单回路，e为为C上任意一条边，则上任意一条边，则C e连通连通. 证证 设设C为为G中一条欧拉回路，任意的中一条欧拉回路，任意的e E(C)，，可知可知C e是是G e的子图，由的子图，由( )知知 C e 连通，所以连通，所以e不为桥不为桥. 332. 证明下图不是哈密顿图证明下图不是哈密顿图. (破坏必要条件破坏必要条件)方法一方法一. 利用定理利用定理15.6，，取取 V1 = {a, c, e, h, j, l}，则，则 p(G V1) = 7 > |V1| = 6 练习练习 2方法二方法二. G为二部图，互补顶点子集为二部图，互补顶点子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}，， |V1| = 6   7 = |V2|. 方法三方法三. 利用可能出现在哈密顿回路上的边至少有利用可能出现在哈密顿回路上的边至少有n(n为阶数为阶数)条条——这也是哈密顿图的一个必要条件，记为（这也是哈密顿图的一个必要条件，记为（ ））. 此图中，此图中，n = 13，，m = 21. 由于由于h, l, j 均为均为4度顶点，度顶点，a, c, e为为3度顶点，且它们关联边互不相同度顶点，且它们关联边互不相同. 而在哈密顿回路上，而在哈密顿回路上，每个顶点准确地关联两条边，于是可能用的边至多有每个顶点准确地关联两条边，于是可能用的边至多有21 (3 2+3 1) = 12. 这达不到（这达不到（ ）的要求）的要求. 343．某次国际会议．某次国际会议8人参加，已知每人至少与其余人参加，已知每人至少与其余7人中的人中的4人人有共同语言，问服务员能否将他们安排在同一张圆桌就座，有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？使得每个人都与两边的人交谈？解解 图是描述事物之间关系的最好的手段之一图是描述事物之间关系的最好的手段之一. 做无向图做无向图G=, 其中其中 V={v| v为与会者为与会者}，， E={(u,v) | u,v V且且u与与v有共同语言，且有共同语言，且u   v}. 易知易知G为简单图且为简单图且 v V, d(v) 4，于是，，于是， u,v V, 有有d(u)+d(v)   8，由定理，由定理15.7 的推论可知的推论可知G为哈密顿图为哈密顿图. 服务服务员在员在G中找一条哈密顿回路中找一条哈密顿回路C，按，按C中相邻关系安排座位即中相邻关系安排座位即可可. 练习练习 3由本题想到的：哈密顿回图的实质是能将图中所有的顶点由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中排在同一个圈中.354. 距离距离(公里公里) 如图所示如图所示. 他如何走行程最短？他如何走行程最短？ 练习练习 4最短的路为最短的路为ABCDA，距离为，距离为36公里，其余两条各为多少？公里，其余两条各为多少？36。