《离散数学-第15章.ppt》由会员分享，可在线阅读，更多相关《离散数学-第15章.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图主要内容主要内容l欧拉图欧拉图l哈密顿图哈密顿图l带权图与货郎担问题带权图与货郎担问题115.1 欧拉图欧拉图历史背景：哥尼斯堡七桥问题与欧拉图历史背景：哥尼斯堡七桥问题与欧拉图2欧拉图定义欧拉图定义定义定义15.1 (1)欧拉通路欧拉通路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的通路点的通路.(2)欧拉回欧拉回路路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的回路点的回路.(3)欧拉图欧拉图具有欧拉回路的图具有欧拉回路的图.(4)半欧拉图半欧拉图具有欧拉通路而无欧拉回路的图具有欧
2、拉通路而无欧拉回路的图.几点说明：几点说明：规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性环不影响图的欧拉性.3上图中，上图中，(1),(4)为欧拉图，为欧拉图，(2),(5)为半欧拉图，为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图既不是欧拉图，也不是半欧拉图.在在(3),(6)中各至少加几条中各至少加几条边才能成为欧拉图？边才能成为欧拉图？欧拉图实例欧拉图实例4无向欧拉图的判别法无向欧拉图的判别法定理定理15.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G连通且无奇
3、度数顶点连通且无奇度数顶点.证证 若若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时如下证明：时如下证明
4、：5PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图并，见示意图3.6欧拉图的判别法欧拉图的判别法定理定理15.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G 连通且恰有两个奇连通且恰有两个奇度顶点度顶点.证证 必要性简单必要性简单.充分性（利用定理充分性（利用定理15.1）设设u,v为为G 中的两个奇度顶点，令中的两个奇度顶点，令 G =G(u,v)则则G 连通且无奇度顶点，由定理连通且无奇度顶点，由定理15.1知知G 为欧拉图，因而为欧拉图，因而存在欧拉回路存在欧拉回路C，令，令 =C(u,v)则则 为为 G 中欧拉
5、通路中欧拉通路.7有向欧拉图的判别法有向欧拉图的判别法定理定理15.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶是强连通的且每个顶点的入度都等于出度点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1.定理定理15.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大中恰有两个奇度顶点，其中一个的入度比出度大1，另一个，另一个的出度比入度大的出度比入度大1，而其余顶点的入度都等于出度，而其余顶点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1.定理
6、定理15.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干是连通的且为若干个边不重的圈之并个边不重的圈之并.可用归纳法证定理可用归纳法证定理15.5.8例题例题例例1 设设G是欧拉图，但是欧拉图，但G不是平凡图，也不是一个环，则不是平凡图，也不是一个环，则(G)2.证证 只需证明只需证明G中不可能有桥（如何证明？）中不可能有桥（如何证明？）上图中，上图中，(1),(2)两两图都是欧拉图，均从图都是欧拉图，均从A点出发，如何点出发，如何一次成功地走出一条欧拉回路来？一次成功地走出一条欧拉回路来？(1)(2)9Fleury算法算法算法：算法：(1)任取任取v0 V(G)，令
7、，令P0=v0.(2)设设Pi=v0e1v1e2eivi 已经行遍，按下面方法从已经行遍，按下面方法从 E(G)e1,e2,ei 中选取中选取ei+1：(a)ei+1与与vi 相关联；相关联；(b)除非无别的边可供行遍，否则除非无别的边可供行遍，否则ei+1不应该为不应该为 Gi=G e1,e2,ei 中的桥中的桥.(3)当当(2)不能再进行时，算法停止不能再进行时，算法停止.可以证明算法停止时所得简单通路可以证明算法停止时所得简单通路 Pm=v0e1v1e2emvm(vm=v0)为为G 中一条欧拉回路中一条欧拉回路.用用Fleury算法走出上一页图算法走出上一页图(1),(2)从从A出发（其
8、实从任何一出发（其实从任何一点点出发都可以）的欧拉回路各一条出发都可以）的欧拉回路各一条.1015.2 哈密顿图哈密顿图历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图 (1)(2)11哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义15.2 (1)哈密顿通路哈密顿通路经过图中所有顶点一次仅一次的通路经过图中所有顶点一次仅一次的通路.(2)哈密顿回路哈密顿回路经过图中所有顶点一次仅一次的回路经过图中所有顶点一次仅一次的回路.(3)哈密顿图哈密顿图具有哈密顿回路的图具有哈密顿回路的图.(4)半哈密顿图半哈密顿图具有哈密顿通路且无哈密顿回路的图具有哈密顿通路且无哈密顿回
9、路的图.几点说明：几点说明：平凡图是哈密顿图平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上哈密顿图的实质是能将图中的所有顶点排在同一个圈上12实例实例在上图中，在上图中，(1),(2)是哈密顿图是哈密顿图;(3)是半哈密顿图是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？既不是哈密顿图，也不是半哈密顿图，为什么？13无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件定理定理15.6 设无向图设无向图G=是哈密顿图，对于任意是
10、哈密顿图，对于任意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|+114几点说明几点说明l定理定理15.6中的条件是哈密顿图的必要条件，但不是充分条中的条件是哈密
11、顿图的必要条件，但不是充分条件（彼得松图）件（彼得松图）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外，其他有桥的图外，其他有
12、桥的图（连通的）均有割点（连通的）均有割点.其实，本例对非简单连通图也对其实，本例对非简单连通图也对.15无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件定理定理15.7 设设G是是n阶无向简单图，若对于任意不相邻的顶点阶无向简单图，若对于任意不相邻的顶点vi,vj，均有，均有 d(vi)+d(vj)n 1 ()则则G 中存在哈密顿通路中存在哈密顿通路.证明线索：证明线索：(1)由由()证证G连通连通(2)=v1v2vl 为为G中极大路径中极大路径.若若l=n,证毕证毕.(3)否则，证否则，证G 中存在过中存在过 上所有顶点的圈上所有顶点的圈C，由，由(1)知知C外外顶顶点存在与点存在与C
13、上某顶点相邻顶点，从而得比上某顶点相邻顶点，从而得比 更长的路径，重更长的路径，重复复(2)(3)，最后得，最后得G中哈密顿通路中哈密顿通路.16证明证明证（着重关键步骤）证（着重关键步骤）(1)由由()及简单图的性质，用反证法证明及简单图的性质，用反证法证明G连通连通.(2)=v1v2vl 为极大路径，为极大路径，l n,若若l=n（结束）（结束）.下面讨论下面讨论ln的情况，即要证的情况，即要证G中存在过中存在过 上所有顶点的圈上所有顶点的圈.若若(v1,vl)在在G中，则中，则(u,v)为为G中圈中圈 否则，设否则，设v1与与 上上 相邻，则相邻，则k 2(否则由否则由极大路径端点性质及
14、极大路径端点性质及()，会得到，会得到d(v1)+d(vl)1+l 24，由定理，由定理15.6可知可知图中无哈密顿回路图中无哈密顿回路.在国际象棋盘上跳马有解，试试看在国际象棋盘上跳马有解，试试看.24设设GG，称称 为为G 的权，并记作的权，并记作W(G)，即，即定定义义15.3 给给定定图图G=，(G为为无向无向图图或有向或有向图图)，设设W:ER(R为实为实数集数集)，对对G中任意中任意边边e=(vi,vj)(G为有向图为有向图时，时，e=)，设，设W(e)=wij，称实数，称实数wij 为边为边e上的上的权权，并将，并将wij标注在边标注在边e上，称上，称G为为带权图带权图，此时常将
15、带权图，此时常将带权图G记作记作.15.3 最短路问题最短路问题与货郎担问题与货郎担问题25货郎担问题货郎担问题设设G=为一个为一个n阶完全带权图阶完全带权图Kn，各边的权非负，且，各边的权非负，且有的边的权可能为有的边的权可能为.求求G中的一条最短的哈密顿回路，这就中的一条最短的哈密顿回路，这就是货郎担问题的数学模型是货郎担问题的数学模型.完全带权图完全带权图Kn（n 3）中不同的哈密顿回路数）中不同的哈密顿回路数(1)Kn中有中有(n 1)!条不同的哈密顿回路（定义意义下）条不同的哈密顿回路（定义意义下）(2)完全带权图中有完全带权图中有(n 1)!条不同的哈密顿回路条不同的哈密顿回路(3
16、)用穷举法解货郎担问题算法的复杂度为用穷举法解货郎担问题算法的复杂度为(n 1)！，当！，当n较较大时，计算量惊人地大大时，计算量惊人地大26 解解 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)27第十五章第十五章 习题课习题课 主要内容主要内容l欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法l哈密顿通路
17、、哈密顿回路、哈密顿图、半哈密顿图哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图l带权图、货郎担问题带权图、货郎担问题基本要求基本要求l深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解欧拉图、半欧拉图的定义及判别定理l深刻理解哈密顿图、半哈密顿图的定义深刻理解哈密顿图、半哈密顿图的定义.l会用哈密顿图的必要条件判断某些图不是哈密顿图会用哈密顿图的必要条件判断某些图不是哈密顿图.l会用充分条件判断某些图是哈密顿图会用充分条件判断某些图是哈密顿图.要特别注意的是，要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要不能将必要条件当作充分条件，也不要将充分条件当必要条件条件.281.设设
18、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方法一：直接证明法方法一：直接证明法.命题命题(
19、*)：设：设C为任意简单回路，为任意简单回路，e为为C上任意一条边，则上任意一条边，则C e连通连通.证证 设设C为为G中一条欧拉回路，任意的中一条欧拉回路，任意的e E(C)，可知可知C e是是G e的子图，由的子图，由()知知 C e 连通，所以连通，所以e不为桥不为桥.292.证明下图不是哈密顿图证明下图不是哈密顿图.(破坏必要条件破坏必要条件)方法一方法一.利用定理利用定理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,
20、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.这达不到（这达不到（）的要求）的要求.303某次国际会议某次国际
21、会议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由本题想到的：哈密顿回图的实质是能将图中所有的顶点由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中排在同一个圈中.314.距离距离(公里公里)如图所示如图所示.他如何走行程最短？他如何走行程最短？练习练习 4最短的路为最短的路为ABCDA，距离为，距离为36公里，其余两条各为多少？公里，其余两条各为多少？32