离散数学第23讲.ppt

1、特殊图,信息学院计算机应用技术系 授课教师：胡静 办公地点：信息楼805 电子邮箱：ise_,第23讲,20:42,2,离散数学 第23讲,回顾上节课内容： 图论中的基本概念 握手定理及推论 完全图及其特征 通路及回路,？,想一想，我们上节课学习了什么？,20:42,3,离散数学 第23讲,本讲基本知识点： 1、欧拉图 欧拉图的定义 欧拉图的判断 2、哈密尔顿图 哈密尔顿图的定义 哈密尔顿图判断的充分条件 3、树 树的定义 最小生成树,？,今天学习什么呢？,20:42,4,18世纪，在俄国哥尼斯堡城（Konnigsberg）（今俄罗斯加里宁格勒）的普莱格尔（Pregel）河上有7座桥河中间有两

2、座岛，岛与河岸之间架有六座桥，另一座桥则连接着两个岛星期天散步已成为当地居民的一种习惯，但试图走过这样的七座桥，而且每桥只走过一次却从来没有成功过直至引起瑞士数学家欧拉(Leonhard Euler，17071783)注意之前，没有人能够解决这个问题,第十五章 欧拉图与哈密尔顿图,20:42,5,第十五章 欧拉图与哈密尔顿图,陆地 岛屿 岛屿 陆地,哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？,20:42,6,第十五章 欧拉图与哈密尔顿图,15.1 欧拉图,定义15.1 通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。 通过图中所有边一次且仅一次行遍所有顶点的

3、回路称为欧拉回路。 具有欧拉回路的图称为欧拉图。 具有欧拉通路而无欧拉回路的图称为半欧拉图。,规定：平凡图是欧拉图。,20:42,7,第十五章 欧拉图与哈密尔顿图,定理15.1 无向图G是欧拉图 G是连通图，且G中没有奇度顶点。,定理15.2 无向图G是半欧拉图 G是连通图，且G中恰有两个奇度顶点。并且这两个奇度结点分别为欧拉通路的起点和终点。,任意两点之间都有通路,20:42,8,解：在图中，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要先走一条边到达b，再走一条欧拉通路，因而它至少要走10条边才

4、能到达c，所以乙必胜。,例15.1(蚂蚁比赛问题),甲、乙两只蚂蚁分别位于右图中的结点a，b处，并设图中的边长 度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？,第十五章 欧拉图与哈密尔顿图,20:42,9,一笔画问题的判断,对于上图，有图(a)能一笔画并且能回到出发点的， 图(b)能一笔画但不能回到出发点的。,第十五章 欧拉图与哈密尔顿图,20:42,10,求欧拉回路的Fleury算法,任取v0V，令P0v0； 设P0v0e1v1e2eivi，按下面的方法从E-e1,e2,ei中选取ei+1： ei+1与vi相关联；

5、除非无别的边可选取，否则ei+1不应该为GG-e1,e2,ei中的桥； 当2）不能再进行时，算法结束。,第十五章 欧拉图与哈密尔顿图,20:42,11,例15.2： Fleury算法应用,在右图所示的欧拉图 中，求从v1出发的欧拉回 路。,如果P4v1e1v2e2v3e3v4e7v7，再往下走（注意别走桥），就可以走出欧拉回路： P4v1e1v2e2v3e3v4e7v7e6v6e5v5e4v4e8v2e9v7e10v1,第十五章 欧拉图与哈密尔顿图,20:42,12,1,11,10,(a),12,9,2,8,3,4,7,5,6,第十五章 欧拉图与哈密尔顿图,桥的实例,桥的实例,20:42,13

6、,1,11,10,(a),12,9,2,8,3,4,7,5,6,goback,第十五章 欧拉图与哈密尔顿图,20:42,14,1,11,10,(a),12,9,2,8,3,4,7,5,6,goback,第十五章 欧拉图与哈密尔顿图,20:42,15,定理15.3 有向图D是欧拉图 D是强连通图且每个顶点的入度都等于出度。,定理15.4 有向图D是半欧拉图 D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。,第十五章 欧拉图与哈密尔顿图,20:42,16,第十五章 欧拉图与哈密尔顿图,答案：图a和图d是欧拉图；图b和图e不是欧拉

7、图，但存在欧拉通路；图c和图f不存在欧拉通路。,练习：判断下列各图是不是欧拉图或半欧拉图。,20:42,17,哈密尔顿图的起源： -周游世界问题,1859年，数学家哈密尔顿创造了一种游戏：他把一个正十二面体的二十个顶点分别标上了世界上二十大城市的名字，把正十二面体的三十条棱解释成连接这些城市之间的交通线。玩法是从某个城市（顶点）出发，沿着这些交通线（边）行走，要求经过每个城市恰好一次，然后回到出发点。他把这个游戏称为“周游世界”。,第十五章 欧拉图与哈密尔顿图,20:42,18,第十五章 欧拉图与哈密尔顿图,15.2 哈密尔顿图 定义15.2 经过图（有向图或无向图）中所有顶点一次且仅一次的通

8、路称为哈密尔顿通路。 经过图中所有顶点一次且仅一次的回路称为哈密尔顿回路。 具有哈密顿回路的图称为哈密尔顿图. 具有哈密顿通路但不具有哈密顿回路的图称为半哈密尔顿图. 规定:平凡图是哈密尔顿图。,20:42,19,第十五章 欧拉图与哈密尔顿图,定理15.7： 设G是n阶无向简单图，若对G中任意不相邻的顶点ui,uj，均有 d(ui)+d(uj)n-1 则G中存在哈密尔顿通路.,推论 设G为n(n 3)阶无向简单图，若对于G中任意两个不相邻的顶点ui,uj，均有 d(ui)+d(uj)n 则G中存在哈密顿回路，从而G为哈密尔顿图。,无向图具有哈密尔顿路与回路的充分条件,20:42,20,利用哈密

9、尔顿图解决实际问题典型例题1：某地有5个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？,解将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密尔顿通路，因此本题有解。,第十五章 欧拉图与哈密尔顿图,20:42,21,第十五章 欧拉图与哈密顿图,典型例题2： 在某次国际会议的预备会中，共有8人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于

10、或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 解 以8个人分别为无向简单图G的顶点，若任意两人vi与vj有共同语言，就vi，vj在之间连无向边(vi，vj) ，则任意一个人vi ,d(vi)为与vi有共同语言的人数。由已知条件可知，任意与vi不相邻的vj （i j） ，均有d(vi)+d(vj)8.由定理15.7的推论可知，G中存在哈密顿回路，按寻找到的回路的顺序安排座次即可。,20:42,22,典型例题2： 今有a,b,c,d,e,f,g7人，已知下列事实： 1）a会讲英语 2）b会讲英语和汉语 3）c会讲英语、意大利语和俄语 4）d会讲日语和汉语 5）e会讲德语和意

11、大利语 6）f会讲法语、日语和俄语 7）g会讲法语和德语 试问这7个人应如何安排座位，才能使每个人和他身边的人交谈？,第十五章 欧拉图与哈密尔顿图,20:42,23,解：设无向图G=,其中 V=a,b,c,d,e,f,g, E=(u,v)|u,v V，且u和v有共同语言。 如右图为连通图，将七人排座围圆桌而坐，使得每个人都能与两边的交谈。即在右图中寻找一条哈密尔顿回路，,第十五章 欧拉图与哈密尔顿图,经观察该回路是abdfgeca,20:42,24,第十六章 树,16.1 无向树及其性质 定义16.1 连通无回路的无向图称为无向树，简称树,常用T表示树。 平凡图称为平凡树。 若无向图G至少有两

12、个连通分支，则称G为森林。 在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。,。,20:42,25,第十六章 树,定理16.1 设G=是n阶m条边的无向图,则下面各命题是等价的： （1）G是树。 （2）G中任意两个顶点之间存在唯一的路径。 （3）G中无回路且m=n-1。 （4）G是连通的且m=n-1。 (5) G是连通的且G中任何边均为桥。 (6) G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。,20:42,26,第十六章 树,（4）G是连通的且m=n-1。 (5) G是连通的且G中任何边均为桥。,证明：（4）（5） 只需证明G中每条

13、边均为桥. 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,vV且u v,则u,v之间存在唯一的路径T ，则T（u,v）(u,v)为加的新边)为G中的圈，显然圈是唯一的。,20:42,27,第十六章 树,(6) G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边

14、的圈。 (1) G是树。,证明：（6）（1）只要证明G是连通的。 u,vV且u v ，则新边(u,v)G产生唯一的圈C，显然有C-(u,v)为G中u到v的通路，故uv,由u,v的任意性可知，G是连通的。,20:42,28,第十六章 树,定理16.2 设T是n阶非平凡的无向树，则T中至少有两片树叶。 证 ：设T有x片树叶，由握手定理及定理16.1可知 2(n-1)=d(vi) x+2(n-x) 解得 x 2.,以上两个定理给出了无向树的主要性质，利用这些性质和握手定理，可以画出阶数n比较小的所有非同构的无向树。,20:42,29,第十六章 树,例16.2 参见课本P375. 练习1：无向树G有5

15、片树叶，3个2度分支点，其余分支点均为3度，问G有多少个顶点？,解： 设G有n个顶点,则有下列关系式 5 1+3 2+(n-5-3) 3=2 (n-1) 解得：n=11,20:42,30,第十六章 树,16.2 生成树 定义16.2 设T是无向图G的子图并且为树，则称T为G的树。 若T是G的树且为生成子图，则称T是G的生成树。 设T是G的生成树， eE(G),若eE(T)，则称e为T的树枝，否则称e为T的弦。 称导出子图GE(G)-E(T) 为T的余树，记作T 。,图中，红色边表示生成树，黑色边组成其余树。可见，余树可能不连通，也可能含回路。,20:42,31,第十六章 树,定义16.5 设无向连通带权图G=,T是G的一棵生成树，T的各边权之和称为T的权，记作W(T).G的所有生成树中权最小的生成树称为G的最小生成树。,Kruskal算法 一种求最小生成树的算法 设n阶无向连通带权图G=有m条边,不妨设G中无环(否则可先删去)，算法为： (1) 将m条边按权从小到大顺序排列，设为e1,e2, ,em。 (2) 取e1在T中，然后依次检查e2, ,em ，若ej (j=2,3, ,m)与T中