离散数学第23讲.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,特殊图,信息学院计算机应用技术系,授课教师：胡静,办公地点：信息楼,805,电子邮箱：,ise_huj,第,23,讲,离散数学 第,23,讲,回顾上节课内容：,图论中的基本概念,握手定理及推论,完全图及其特征,通路及回路,想一想，我们上节课学习了什么？,7/7/2026,2,离散数学 第,23,讲,本讲基本知识点：,1,、欧拉图,欧拉图的定义,欧拉图的判断,2,、哈密尔顿图,哈密尔顿图的定义,哈密尔顿图判断的充分条件,3,、树,树的定义,最小生成树,今天学习什么呢？,7/7/2026,3,18,世纪，在俄国哥尼斯堡城（,Konnigsberg,）（今俄罗斯加里宁格勒）的普莱格尔（,Pregel,）河上有,7,座桥河中间有两座岛，岛与河岸之间架有六座桥，另一座桥则连接着两个岛星期天散步已成为当地居民的一种习惯，但试图走过这样的七座桥，而且每桥只走过一次却从来没有成功过直至引起瑞士数学家欧拉,(,Leonhard,Euler,，,17071783),注意之前，没有人能够解决这个问题,第十五章 欧拉图与哈密尔顿图,7/7/2026,4,第十五章 欧拉图与哈密尔顿图,陆地,岛屿 岛屿,陆地,哥尼斯堡七桥问题,如何不重复地走完七桥后回到起点？,。,。,。,A,B,C,D,7/7/2026,5,第十五章 欧拉图与哈密尔顿图,15.1,欧拉图,定义,15.1,通过图,(,无向图或有向图,),中所有边一次且仅一次行遍所有顶点的通路称为,欧拉通路,。,通过图中所有边一次且仅一次行遍所有顶点的回路称为,欧拉回路,。,具有欧拉回路的图称为,欧拉图,。,具有欧拉通路而无欧拉回路的图称为,半欧拉图,。,规定：,平凡图是欧拉图。,7/7/2026,6,第十五章 欧拉图与哈密尔顿图,定理,15.1,无向图,G,是欧拉图,G,是连通图，且,G,中没有奇度顶点。,定理,15.2,无向图,G,是半欧拉图,G,是连通图，且,G,中恰有两个奇度顶点。并且这两个奇度结点分别为欧拉通路的起点和终点。,任意两点之间都有通路,7/7/2026,7,解：,在图中，仅有两个度数为奇数的结点,b,，,c,，,因而存在从,b,到,c,的欧拉通路，蚂蚁乙走到,c,只要走一条欧拉通路，边数为,9,条。而蚂蚁甲要想走完所有的边到达,c,，,至少要先走一条边到达,b,，,再走一条欧拉通路，因而它至少要走,10,条边才能到达,c,，,所以乙必胜。,例,15.1(,蚂蚁比赛问题,),甲、乙两只蚂蚁分别位于右图中的结点,a,，,b,处，并设图中的边长,度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点,c,处。如果它们的速度相同，问谁先到达目的地？,c,b(,乙,),a(,甲,),第十五章 欧拉图与哈密尔顿图,7/7/2026,8,一笔画问题的判断,对于上图，有,图,(a),能一笔画并且能回到出发点的，,图,(b),能一笔画但不能回到出发点的。,1,11,10,(a),12,9,2,8,3,4,7,5,6,1,2,3,4,5,(b),第十五章 欧拉图与哈密尔顿图,7/7/2026,9,求欧拉回路的,Fleury,算法,任取,v0V,，令,P0,v0,；,设,P0,v0e1v1e2,eivi,，,按下面的方法从,E-e1,e2,ei,中选取,ei+1,：,ei+1,与,vi,相关联；,除非无别的边可选取，否则,ei+1,不应该为,G,G-e1,e2,ei,中的桥；,当,2,）不能再进行时，算法结束。,第十五章 欧拉图与哈密尔顿图,7/7/2026,10,例,15.2,：,Fleury,算法应用,在,右图所示的欧拉图,中，求从,v1,出发的欧拉回,路。,如果,P,4,v,1,e,1,v,2,e,2,v,3,e,3,v,4,e,7,v,7,，,再往下走（注意别走桥），就可以走出欧拉回路：,P,4,v,1,e,1,v,2,e,2,v,3,e,3,v,4,e,7,v,7,e,6,v,6,e,5,v,5,e,4,v,4,e,8,v,2,e,9,v,7,e,10,v,1,第十五章 欧拉图与哈密尔顿图,7/7/2026,11,1,11,10,(a),12,9,2,8,3,4,7,5,6,第十五章 欧拉图与哈密尔顿图,桥的实例,桥的实例,7/7/2026,12,1,11,10,(a),12,9,2,8,3,4,7,5,6,goback,第十五章 欧拉图与哈密尔顿图,7/7/2026,13,1,11,10,(a),12,9,2,8,3,4,7,5,6,goback,第十五章 欧拉图与哈密尔顿图,7/7/2026,14,定理,15.3,有向图,D,是欧拉图,D,是强连通图且每个顶点的入度都等于出度。,定理,15.4,有向图,D,是半欧拉图,D,是单向连通的，且,D,中恰有两个奇度顶点，其中一个的入度比出度大,1,，另一个的出度比入度大,1,，而其余顶点的入度都等于出度。,第十五章 欧拉图与哈密尔顿图,7/7/2026,15,第十五章 欧拉图与哈密尔顿图,答案：图,a,和图,d,是欧拉图；图,b,和图,e,不是欧拉图，但存在欧拉通路；图,c,和图,f,不存在欧拉通路。,练习：判断下列各图是不是欧拉图或半欧拉图。,7/7/2026,16,哈密尔顿图的起源：,-,周游世界问题,1859,年，数学家哈密尔顿创造了一种游戏：他把一个正十二面体的二十个顶点分别标上了世界上二十大城市的名字，把正十二面体的三十条棱解释成连接这些城市之间的交通线。玩法是从某个城市（顶点）出发，沿着这些交通线（边）行走，要求经过每个城市恰好一次，然后回到出发点。他把这个游戏称为,“,周游世界,”,。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,第十五章 欧拉图与哈密尔顿图,7/7/2026,17,第十五章 欧拉图与哈密尔顿图,15.2,哈密尔顿图,定义,15.2,经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为,哈密尔顿通路,。,经过图中所有顶点一次且仅一次的回路称为,哈密尔顿回路,。,具有哈密顿回路的图称为,哈密尔顿图,.,具有哈密顿通路但不具有哈密顿回路的图称为,半哈密尔顿图,.,规定,:,平凡图是哈密尔顿图。,7/7/2026,18,第十五章 欧拉图与哈密尔顿图,定理,15.7,：,设,G,是,n,阶无向简单图，若对,G,中任意不相邻的顶点,u,i,u,j,，,均有,d(,u,i,)+d(,u,j,)n-1,则,G,中存在哈密尔顿通路,.,推论,设,G,为,n(n 3),阶无向简单图，若对于,G,中任意两个不相邻的顶点,u,i,u,j,，,均,有,d(,u,i,)+d(,u,j,)n,则,G,中存在哈密顿回路，从而,G,为哈密尔顿图。,无向图具有哈密尔顿路与回路的充分条件,7/7/2026,19,利用哈密尔顿图解决实际问题典型例题,1,：,某地有,5,个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这,5,处？,解,将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密尔顿通路，因此本题有解。,第十五章 欧拉图与哈密尔顿图,7/7/2026,20,第十五章 欧拉图与哈密顿图,典型例题,2,：,在某次国际会议的预备会中，共有,8,人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于,8,，问能否将这,8,个人排在圆桌旁，使其任何人都能与两边的人交谈。,解,以,8,个人分别为无向简单图,G,的顶点，若任意两人,v,i,与,v,j,有共同语言，就,v,i,，,v,j,在之间连无向边,(v,i,，,v,j,),，则,任意一个人,v,i,d(v,i,),为与,v,i,有共同语言的人数。由已知条件可知，任意与,v,i,不相邻的,v,j,（,i j,）,，,均有,d(v,i,)+d(,v,j,)8.,由定理,15.7,的推论可知，,G,中存在哈密顿回路，按寻找到的回路的顺序安排座次即可。,7/7/2026,21,典型例题,2,：,今有,a,b,c,d,e,f,g7,人，已知下列事实：,1,）,a,会讲英语,2,）,b,会讲英语和汉语,3,）,c,会讲英语、意大利语和俄语,4,）,d,会讲日语和汉语,5,）,e,会讲德语和意大利语,6,）,f,会讲法语、日语和俄语,7,）,g,会讲法语和德语,试问这,7,个人应如何安排座位，才能使每个人和他身边的人交谈？,第十五章 欧拉图与哈密尔顿图,7/7/2026,22,解：设无向图,G=,其中,V=,a,b,c,d,e,f,g,E=(,u,v,),|u,v,V,，且,u,和,v,有共同语言,。,如右图为连通图，将七人排座围圆桌而坐，使得每个人都能与两边的交谈。即在右图中寻找一条哈密尔顿回路，,第十五章 欧拉图与哈密尔顿图,f,g,e,c,a,b,d,经观察该回路是,abdfgeca,7/7/2026,23,第十六章 树,16.1,无向树及其性质,定义,16.1,连通无回路的无向图称为,无向树,，简称,树,常用,T,表示树。,平凡图称为,平凡树。,若无向图,G,至少有两个连通分支，则称,G,为,森林,。,在无向树中，悬挂顶点称为,树叶,，度数大于或等于,2,的顶点称为,分支点,。,。,。,。,。,。,。,。,7/7/2026,24,第十六章 树,定理,16.1,设,G=,是,n,阶,m,条边的无向图,则下面各命题是等价的：,（,1,）,G,是树。,（,2,）,G,中任意两个顶点之间存在唯一的路径。,（,3,）,G,中无回路且,m=n-1,。,（,4,）,G,是连通的且,m=n-1,。,(5)G,是连通的且,G,中任何边均为桥。,(6)G,中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。,7/7/2026,25,第十六章 树,（,4,）,G,是连通的且,m=n-1,。,(5)G,是连通的且,G,中任何边均为桥。,证明：,（,4,）,（,5,）,只需证明,G,中每条边均为桥,.,eE,，,均有,E(G-e)=n-1-1=n-2,，,由于,n,阶图,G,是连通的至少需要,n-1,条边，所以,G-e,已不是连通图，故,e,为桥。,(5)G,是连通的且,G,中任何边均为桥。,(6)G,中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。,证明：,（,5,）,（,6,）,由于,G,中每条边均为桥，因而,G,中无圈，又由于,G,连通，所以,G,为树。对于,u,v,V,且,u v,则,u,v,之间存在唯一的路径,T,，则,T,（,u,v,）,(,(u,v),为加的新边,),为,G,中的圈，显然圈是唯一的。,7/7/2026,26,第十六章 树,(6)G,中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。,(1)G,是树。,证明：,（,6,）,（,1,）,只要证明,G,是连通的。,u,v,V,且,u v,，,则新边,(u,v)G,产生唯一的圈,C,，,显然有,C-(u,v),为,G,中,u,到,v,的通路，故,u,v,由,u,v,的任意性可知，,G,是连通的。,7/7/2026,27,第十六章 树,定理,16.2,设,T,是,n,阶非平凡的无向树，则,T,中至少有两片树叶。,证,：设,T,有,x,片树叶，由握手定理及定理,16.1,可知,2(n-1)=,d(v,i,),x+2(n-x),解得,x,2.,以上两个定理给出了无向树的主要性质，利用这些性质和握手定理，可以画出阶数,n,比较小的所有非同构的无向树。,7/7/2026,28,第十六章 树,例,16.2,参见课本,P,375,.,练习,1,：无向树,G,有,5,片树叶，,3,个,2,度分支点，其余分支点均为,3,度，问,G,有多少个顶点？,解：,设,G,有,n,个顶点,则有下列关系式,5,1+3 2+(n-5-3)3=2(n-1),解得：,n=11,7/7/2026,29,第十六章 树,16.2,生成树,定义,16.2,设,T,是无向图,G,的子图并且为树，则称,T,为,G,的,树,。,若,T,是,G,的树且为生成子图，则称,T,是,G,的,生成树,。,设,T,是,G,的生成树，,e,E(G),若,eE(T),，,则称,e,为,T,的,树枝,，否则称,e,为,T,的,弦,。,称导出子图,GE(G)-E(T),为,T,的,余树,，记作,T,。,图,中，,红色边,表示生成树，,黑色边,组成其余树。可见，余树可能不连通，也可能含回路。,7/7/2026,30,第十六章 树,定义,16.5,设无向连通带权图,G=,T,是,G,的一棵,生成树，,T,的各边权之和,称为,T,的,权,，记作,W(T).G,的所有生成树中权最小的生成树称为,G,的,最小生成树,。,Kruskal,算法,一种求最小生成树的算法,设,n,阶无向连通带权图,G=,有,m,条边,不妨设,G,中无,环,(,否则可先删去,),，算法为：,(1),将,m,条边按权从小到大顺序排列，设为,e,1,e,2,e,m,。,(2),取,e,1,在,T,中，然后依次检查,e,2,e,m,，若,e,j,(j=2,3,m),与,T,中的边不能构成回路，则取,e,j,在,T,中，否则放弃,e,j,，,考虑下一条边，直至,jm,。,(3),算法停止时得到的,T,为,G,的最小生成树。,7/7/2026,31,第十六章 树,例：,用,Kruskal,算法求下图的最小生成树。,2,1,2,1,3,4,3,1,5,1,1,3,1,。,。,。,。,。,OK!,。,。,。,。,。,。,。,2,1,4,5,1,5,5,4,5,3,3,2,练习：,求下图的最小生成树。,7/7/2026,32,本讲小结,1,、掌握欧拉图的定义,2,、掌握判断欧拉图的方法,3,、哈密尔顿图的定义,4,、掌握判断哈密尔顿图的方法（充分条件）,5,、掌握树的定义,6,、最小生成树及其算法,作业：,P304,第,9,题,离散数学 第,23,讲,7/7/2026,33,