《离散数学(第十五章)》由会员分享，可在线阅读，更多相关《离散数学(第十五章)（36页珍藏版）》请在金锄头文库上搜索。
1、1,第十五章 欧拉图与哈密顿图,主要内容 欧拉图 哈密顿图 带权图与货郎担问题,2,第十五章 欧拉图与哈密顿图,预备知识 无向图G = d(v), d+(v), d(v) 奇度顶点与偶度顶点 连通，通路，回路,3,瑞士数学家，最多产的数学家 1100书籍论文 全集75卷 13个孩子 最后17年失明,Question: 如何将左边图所示的七桥问题转换为点和边来描述? 一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？,Link to the video,Leonhard Euler:17071783,历史背景,4,下面哪些图形可以一笔画，哪些图形不能一笔画？,试一试：,(1),(2),
2、(3),(4),(5),(6),5,（2）,（2）,（3）,（3）,6,中途点特征：,笔沿着某条边进去后，必定沿另一条边出去，于是知道与中途点为端点的边必定是成对出现的，这样中途点必定是偶点。,进去,出来,进去,出来,如果起点和终点重合，则与他们相连的边是偶数条，所以也是偶点 起点和终点不重合，与他们相连的边奇数条，则是都是奇点,“一笔画”图形特征：一个图形可以“一笔画”则奇点的个数是0个或2个,7,欧拉图定义,定义15.1 (1) 欧拉通路经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图具有欧拉回路的图. (4)
3、半欧拉图具有欧拉通路而无欧拉回路的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是生成的简单通路，欧拉回路是生成的简单回路. 环不影响图的欧拉性.,8,上图中，(1) ,(4) 为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图. 在(3),(6)中各至少加几条边才能成为欧拉图？,欧拉图实例,9,无向欧拉图的判别法,定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 证 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图. 必要性 设C 为G 中一条欧拉回路. (1) G 连通显然. (2) viV(G)，vi在C上每出现一次获2度，所以vi为偶
4、度顶点. 由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）. (1) m=1时，G为一个环，则G为欧拉图. (2) 设mk（k1）时结论为真，m=k+1时如下证明：,10,PLAY,从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3.,11,欧拉图的判别法,定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点. 证 必要性简单. 充分性（利用定理15.1） 设u,v为G 中的两个奇度顶点，令 G =G(u,v) 则G 连通且无奇度顶点，由定理15.1知G 为欧拉图，因而 存在欧拉回路C，令 =C(u,v) 则 为 G 中欧拉通路.,12,下图是
5、某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个出口，问游人能否一次不重复地穿过所有的门，并且从入口进，从出口出？,练习 1,13,下图是一个公园的平面图.要使游客走遍每条路而不重复，问出入口应设在哪里？,练习 2,14,有向欧拉图的判别法,定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且 D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个 的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理
6、15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理15.5.,15,查阅有关欧拉图应用研究的文献 书面总结: 研究动机 研究框架 关键的发现 结论,作业,16,15.2 哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,(1) (2),17,18,哈密顿图与半哈密顿图,定义15.2 (1) 哈密顿通路经过图中所有顶点一次仅一次的通路. (2) 哈密顿回路经过图中所有顶点一次仅一次的回路. (3) 哈密顿图具有哈密顿回路的图. (4) 半哈密顿图具有哈密顿通路且无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路，哈密顿回路是初级回路
7、. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上,19,实例,在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？,20,无向哈密顿图的一个必要条件,定理15.6 设无向图G=是哈密顿图，对于任意V1V且 V1，均有 p(GV1) |V1|,证 设C为G中一条哈密顿回路 (1) p(CV1) |V1| (2) p(GV1) p(CV1) |V1| （因为CG）,推论 设无向图G=是半哈密顿图，对于任意的V1V且V1均有 p(GV1) |V1|+1,证 令 uv为G中哈密顿通路，令G = G(u,v)，则
8、G为哈密顿图. 于是 p(GV1) = p(GV1(u,v) |V1|+1,21,(1)若G是哈密顿图，则一定满足上式； (2)满足上式却不一定是哈密顿图； (3)不满足上式一定不是哈密顿图。,22,定理应用举例,利用定理说明下图不是哈密顿图。,23,解答,取S=v1,v4，则：|S|=2,p(V-S)=3，,不满足： p(V-S)|S|,不是哈密顿图,24,几点说明,由定理15.6立刻可知，Kr,s当sr+1时不是哈密顿图. 易知Kr,r（r2）时都是哈密顿图，Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图. 例2 设G为n阶无向连通简单图，若G中有割点或桥，则G不
9、是哈密顿图. 证 设v为割点，则 p(Gv) 2|v|=1. K2有桥，它显然不是哈密顿图. 除K2外，其他有桥的图（连通的）均有割点. 其实，本例对非简单连通图也对.,25,无向哈密顿图的一个充分条件,定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有 d(vi)+d(vj) n1 () 则G 中存在哈密顿通路.,推论 设G为n (n3) 阶无向简单图，若对于G中任意两个 不相邻的顶点vi,vj，均有 d(vi)+d(vj) n （） 则G中存在哈密顿回路，从而G为哈密顿图.,26,几点说明,由定理15.7的推论可知，Kn（n3）均为哈密顿图.,(1)满足上式一定是哈
10、密顿图； (2)是哈密顿图不一定满足上式； (3)不是哈密顿图一定不满足上式。,完全图Kn (n3) 中任何两个顶点u,v，均有 d(u)+d(v) = 2(n1) n（n3）， 所以Kn为哈密顿图.,27,定理应用举例,任意两点的度之和为4 n=6 不满足d(vi)+d(vj) n 但却是哈密顿图， 也有哈密顿路径。,是哈密顿图,28,n（n2）阶竞赛图中存在哈密顿通路 定理15.9 若D为n（n2）阶竞赛图，则D中具有哈密顿通路 证明思路：注意，竞赛图的基图是无向完全图. 对n（n2） 做归纳. 只需观察下面两个图.,无向哈密顿图的充分条件,29,设GG，称 为G的权，并记作W(G)，即,
11、定义15.3 给定图G = ，(G为无向图或有向图)，设 W:ER (R为实数集)，对G中任意边e = (vi,vj) (G为有向图 时，e = )，设W(e) = wij，称实数wij 为边e上的权，并将 wij标注在边e上，称G为带权图，此时常将带权图G记作 .,15.3 最短路问题与货郎担问题,30,例：一位旅客要从A城到B城 他希望选择一条途中中转次数最少的路线； 他希望选择一条途中所花时间最短的路线； 他希望选择一条途中费用最小的路线；,这些问题均是带权图上的最短路径问题。,边上的权表示一站 边上的权代表距离 边的权代表费用,31,货郎担问题,设G=为一个n阶完全带权图Kn，各边的权
12、非负，且 有的边的权可能为. 求G中的一条最短的哈密顿回路，这就 是货郎担问题的数学模型. 完全带权图Kn（n3）中不同的哈密顿回路数 (1) Kn中有(n1)! 条不同的哈密顿回路（定义意义下） (2) 完全带权图中有(n1)! 条不同的哈密顿回路 (3) 用穷举法解货郎担问题算法的复杂度为(n1)！，当n较大时，计算量惊人地大,32,解 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
13、),33,1. 设G为n（n2）阶无向欧拉图，证明G中无桥(见例1思考题),方法二：反证法. 利用欧拉图无奇度顶点及握手定理的推论. 否则，设e=(u,v)为G中桥，则Ge产生两个连通分支G1, G2，不妨设u在G1中，v在G2中. 由于从G中删除e时，只改变u,v 的度数(各减1)，因而G1与G2中均只含一个奇度顶点，这与握手定理推论矛盾.,练习1,方法一：直接证明法. 命题 (*)：设C为任意简单回路，e为C上任意一条边，则Ce连通. 证 设C为G中一条欧拉回路，任意的eE(C)，可知Ce是Ge的子图，由()知 Ce 连通，所以e不为桥.,34,2. 证明下图不是哈密顿图. (破坏必要条件
14、),方法一. 利用定理15.6， 取 V1 = a, c, e, h, j, l，则 p(GV1) = 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 度顶点，且它们关联边互不相同. 而在哈密顿回路上， 每个顶点准确地关联两条边，于是可能用的边至
15、多有21(32+31) = 12. 这达不到（）的要求.,35,3某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？,解 图是描述事物之间关系的最好的手段之一. 做无向图G=, 其中 V=v| v为与会者， E=(u,v) | u,vV且u与v有共同语言，且u v. 易知G为简单图且vV, d(v)4，于是，u,vV, 有d(u)+d(v) 8，由定理15.7 的推论可知G为哈密顿图. 服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.,练习 3,由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.,36,4. 距离(公里) 如图所示. 他如何走行程最短？,练习 4,最短的路为ABCDA，距离为36公里，其余两条各为多少？,
