离散数学第23讲课件.ppt

1、12/26/20221信息学院计算机应用技术系信息学院计算机应用技术系授课教师：胡静授课教师：胡静办公地点：信息楼办公地点：信息楼805电子邮箱：电子邮箱：ise_ 第第23讲讲12/26/20222离散数学离散数学 第第2323讲讲回顾上节课内容：回顾上节课内容：l图论中的基本概念图论中的基本概念l握手定理及推论握手定理及推论l完全图及其特征完全图及其特征l通路及回路通路及回路12/26/20223离散数学离散数学 第第2323讲讲本讲基本知识点：本讲基本知识点：l1、欧拉图、欧拉图 欧拉图的定义欧拉图的定义 欧拉图的判断欧拉图的判断l2、哈密尔顿图、哈密尔顿图 哈密尔顿图的定义哈密尔顿图的

2、定义 哈密尔顿图判断的充分条件哈密尔顿图判断的充分条件l3、树、树 树的定义树的定义 最小生成树最小生成树12/26/20224 18 18世纪，在俄国哥尼斯堡城世纪，在俄国哥尼斯堡城（KonnigsbergKonnigsberg）（今俄罗斯加里宁）（今俄罗斯加里宁格勒）的普莱格尔（格勒）的普莱格尔（PregelPregel）河上）河上有有7 7座桥河中间有两座岛，岛与河座桥河中间有两座岛，岛与河岸之间架有六座桥，另一座桥则连岸之间架有六座桥，另一座桥则连接着两个岛星期天散步已成为当接着两个岛星期天散步已成为当地居民的一种习惯，但试图走过这地居民的一种习惯，但试图走过这样的七座桥，而且每桥只走

3、过一次样的七座桥，而且每桥只走过一次却从来没有成功过直至引起瑞士却从来没有成功过直至引起瑞士数学家欧拉数学家欧拉(Leonhard Euler(Leonhard Euler，17071783)17071783)注意之前，没有人能够注意之前，没有人能够解决这个问题解决这个问题第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/20225第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图 陆地陆地 岛屿岛屿 岛屿岛屿 陆地陆地哥尼斯堡七桥问题哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？。12/26/20226第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图15.1 1

4、5.1 欧拉图欧拉图定义定义15.115.1通过图通过图(无向图或有向图无向图或有向图)中所有边一次且仅一次行遍所中所有边一次且仅一次行遍所有顶点的通路称为有顶点的通路称为欧拉通路欧拉通路。通过图中所有边一次且仅一次行遍所有顶点的回路称为通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路欧拉回路。具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图。具有欧拉通路而无欧拉回路的图称为具有欧拉通路而无欧拉回路的图称为半欧拉图半欧拉图。规定：规定：平凡图是欧拉图。平凡图是欧拉图。12/26/20227第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图定理定理15.115.1无向图无向图G

5、G是欧拉图是欧拉图 G G是连通图，且是连通图，且G G中没有奇度顶点。中没有奇度顶点。定理定理15.215.2无向图无向图G G是半欧拉图是半欧拉图 G G是连通图，且是连通图，且G G中恰有两个奇度中恰有两个奇度顶点。并且这两个奇度结点分别为欧拉通路的起点和终点。顶点。并且这两个奇度结点分别为欧拉通路的起点和终点。任意两点之间都有通路12/26/20228解：解：在图中，仅有两个度数为奇数的结点在图中，仅有两个度数为奇数的结点b b，c c，因而存在从，因而存在从b b到到c c的欧拉通路，蚂蚁乙走到的欧拉通路，蚂蚁乙走到c c只要走一条欧拉通路，边数只要走一条欧拉通路，边数为为9 9条。

6、而蚂蚁甲要想走完所有的边到达条。而蚂蚁甲要想走完所有的边到达c c，至少要先走一条，至少要先走一条边到达边到达b b，再走一条欧拉通路，因而它至少要走，再走一条欧拉通路，因而它至少要走1010条边才能条边才能到达到达c c，所以乙必胜。，所以乙必胜。例例15.1(15.1(蚂蚁比赛问题蚂蚁比赛问题)甲、乙两只蚂蚁分别位于右图中甲、乙两只蚂蚁分别位于右图中的结点的结点a a，b b处，并设图中的边长处，并设图中的边长度是相等的。甲、乙进行比赛：度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图从它们所在的结点出发，走过图中的所有边最后到达结点中的所有边最后到达结点c c处。如处。如果它们的

7、速度相同，问谁先到达果它们的速度相同，问谁先到达目的地？目的地？c cb(b(乙乙)a(a(甲甲)第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/20229一笔画问题的判断一笔画问题的判断对于上图，有对于上图，有图图(a)(a)能一笔画并且能回到出发点的，能一笔画并且能回到出发点的，图图(b)(b)能一笔画但不能回到出发点的。能一笔画但不能回到出发点的。1 111111010(a)(a)12129 92 28 83 34 47 75 56 61 12 23 34 45 5(b)(b)第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/202210求欧拉回路的求欧

8、拉回路的Fleury算法算法任取任取v0Vv0V，令，令P0P0v0v0；设设P0P0v0e1v1e2eiviv0e1v1e2eivi，按下面的方法从，按下面的方法从E-E-e1,e2,eie1,e2,ei中选取中选取ei+1ei+1：ei+1ei+1与与vivi相关联；相关联；除非无别的边可选取，否则除非无别的边可选取，否则ei+1ei+1不应该为不应该为GGG-G-e1,e2,eie1,e2,ei中的桥；中的桥；当当2 2）不能再进行时，算法结束。）不能再进行时，算法结束。第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/202211例例15.2：Fleury算法应用算法应

9、用在右图所示的欧拉图在右图所示的欧拉图中，求从中，求从v1v1出发的欧拉回出发的欧拉回路。路。如果如果P P4 4v v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e7 7v v7 7，再往下走（注意别，再往下走（注意别走桥），就可以走出欧拉回路：走桥），就可以走出欧拉回路：P P4 4v v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e7 7v v7 7e e6 6v v6 6e e5 5v v5 5e e4 4v v4 4e e8 8v v2 2e e9 9v v7 7e e1010v v1 1第十五章第十五章 欧

10、拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/2022121 111111010(a)(a)12129 92 28 83 34 47 75 56 6第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图桥的实例桥的实例12/26/2022131 111111010(a)(a)12129 92 28 83 34 47 75 56 6goback第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/2022141 111111010(a)(a)12129 92 28 83 34 47 75 56 6goback第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/20221

11、5定理定理15.315.3有向图有向图D D是欧拉图是欧拉图 D是强连通图且每个顶点的入度都是强连通图且每个顶点的入度都等于出度。等于出度。定理定理15.415.4有向图有向图D D是半欧拉图是半欧拉图 D是单向连通的，且是单向连通的，且D D中恰有两个中恰有两个奇度顶点，其中一个的入度比出度大奇度顶点，其中一个的入度比出度大1 1，另一个的出度比，另一个的出度比入度大入度大1 1，而其余顶点的入度都等于出度。，而其余顶点的入度都等于出度。第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/202216第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图答案：图答案：图a a和

12、图和图d d是欧拉图；图是欧拉图；图b b和图和图e e不是欧拉图，但存不是欧拉图，但存在欧拉通路；图在欧拉通路；图c c和图和图f f不存在欧拉通路。不存在欧拉通路。练习：判断下列各图是不是欧拉图或半欧拉图。练习：判断下列各图是不是欧拉图或半欧拉图。12/26/202217哈密尔顿图的起源：哈密尔顿图的起源：-周游世界问题周游世界问题18591859年，数学家哈密尔顿创造了一种游戏：他把一个正十二年，数学家哈密尔顿创造了一种游戏：他把一个正十二面体的二十个顶点分别标上了世界上二十大城市的名字，把面体的二十个顶点分别标上了世界上二十大城市的名字，把正十二面体的三十条棱解释成连接这些城市之间的交

13、通线。正十二面体的三十条棱解释成连接这些城市之间的交通线。玩法是从某个城市（顶点）出发，沿着这些交通线（边）行玩法是从某个城市（顶点）出发，沿着这些交通线（边）行走，要求经过每个城市恰好一次，然后回到出发点。他把这走，要求经过每个城市恰好一次，然后回到出发点。他把这个游戏称为个游戏称为“周游世界周游世界”。1 12 23 34 45 56 67 78 89 910101111121213131414151516161717181819192020第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/202218第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图15.2 15.2

14、 哈密尔顿图哈密尔顿图定义定义15.2 15.2 v经过图（有向图或无向图）中所有顶点一次且仅一次的通路经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为称为哈密尔顿通路哈密尔顿通路。v经过图中所有顶点一次且仅一次的回路称为经过图中所有顶点一次且仅一次的回路称为哈密尔顿回路哈密尔顿回路。v具有哈密顿回路的图称为具有哈密顿回路的图称为哈密尔顿图哈密尔顿图.v具有哈密顿通路但不具有哈密顿回路的图称为具有哈密顿通路但不具有哈密顿回路的图称为半哈密尔顿图半哈密尔顿图.规定规定:平凡图是哈密尔顿图。平凡图是哈密尔顿图。12/26/202219第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图定

15、理定理15.715.7：设设G G是是n n阶无向简单图，若对阶无向简单图，若对G G中任意不相邻的顶点中任意不相邻的顶点u ui i,u,uj j，均有均有 d(ud(ui i)+d(u)+d(uj j)n-1 )n-1 则则G G中存在哈密尔顿通路中存在哈密尔顿通路.推论推论 设设G G为为n(n 3)n(n 3)阶无向简单图，若对于阶无向简单图，若对于G G中任意两个不中任意两个不相邻的顶点相邻的顶点u ui i,u,uj j，均有均有 d(ud(ui i)+d(u)+d(uj j)n)n 则则G G中存在哈密顿回路，从而中存在哈密顿回路，从而G G为哈密尔顿图。为哈密尔顿图。无向图具有

16、哈密尔顿路与回路的充分条件无向图具有哈密尔顿路与回路的充分条件12/26/202220利用哈密尔顿图解决实际问题利用哈密尔顿图解决实际问题典型例题典型例题1 1：某地有某地有5 5个风景点，若每个风景点个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这每个风景点恰好一次而游完这5 5处？处？解解将将5 5个风景点看成是有个风景点看成是有5 5个结点的无向图，两风个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均两条道路与其

17、他结点相通，故每个结点的度数均为为2 2，从而任意两个不相邻的结点的度数之和等于，从而任意两个不相邻的结点的度数之和等于4 4，正好为总结点数减，正好为总结点数减1 1。故此图中存在一条哈密。故此图中存在一条哈密尔顿通路，因此本题有解。尔顿通路，因此本题有解。第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/202221第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图典型例题典型例题2 2：在某次国际会议的预备会中，共有在某次国际会议的预备会中，共有8 8人参人参加，他们来自不同的国家，已知他们中任何两个无共同语加，他们来自不同的国家，已知他们中任何两个无共同语言的人中的每一

18、个，与其余有共同语言的人数之和大于或言的人中的每一个，与其余有共同语言的人数之和大于或等于等于8 8，问能否将这，问能否将这8 8个人排在圆桌旁，使其任何人都能与个人排在圆桌旁，使其任何人都能与两边的人交谈。两边的人交谈。解解 以以8 8个人分别为无向简单图个人分别为无向简单图G G的顶点，若任意两人的顶点，若任意两人v vi i与与v vj j有共同语言，就有共同语言，就v vi i，v vj j在之间连无向边在之间连无向边(v(vi i，v vj j)，则，则任意一个人任意一个人v vi i,d(v,d(vi i)为与为与v vi i有共同语言的人数。由已知条有共同语言的人数。由已知条件可

19、知，任意与件可知，任意与v vi i不相邻的不相邻的v vj j（i ji j），均有，均有d(vd(vi i)+d(v)+d(vj j)8.)8.由定理由定理15.715.7的推论可知，的推论可知，G G中存在哈密顿中存在哈密顿回路，按寻找到的回路的顺序安排座次即可。回路，按寻找到的回路的顺序安排座次即可。12/26/202222典型例题典型例题2 2：今有今有a,b,c,d,e,f,g7a,b,c,d,e,f,g7人，已知下列事实：人，已知下列事实：1 1）a a会讲英语会讲英语2 2）b b会讲英语和汉语会讲英语和汉语3 3）c c会讲英语、意大利语和俄语会讲英语、意大利语和俄语4 4）

20、d d会讲日语和汉语会讲日语和汉语5 5）e e会讲德语和意大利语会讲德语和意大利语6 6）f f会讲法语、日语和俄语会讲法语、日语和俄语7 7）g g会讲法语和德语会讲法语和德语试问这试问这7 7个人应如何安排座位，才能使每个人和他身边的人个人应如何安排座位，才能使每个人和他身边的人交谈？交谈？第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图12/26/202223解：设无向图解：设无向图G=,G=,其中其中V=a,b,c,d,e,f,g,V=a,b,c,d,e,f,g,E=(u,v)|u,v E=(u,v)|u,v VV，且，且u u和和v v有共同语言有共同语言。如右图为连通图，将

21、七人排座围圆桌而坐，使得每个人都如右图为连通图，将七人排座围圆桌而坐，使得每个人都能与两边的交谈。即在右图中寻找一条哈密尔顿回路，能与两边的交谈。即在右图中寻找一条哈密尔顿回路，第十五章第十五章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图fgecabd经观察该回路是经观察该回路是abdfgecaabdfgeca12/26/202224第十六章第十六章 树树16.1 16.1 无向树及其性质无向树及其性质定义定义16.1 16.1 v连通无回路的无向图称为连通无回路的无向图称为无向树无向树，简称，简称树树,常用常用T T表示树。表示树。v平凡图称为平凡图称为平凡树。平凡树。v若无向图若无向图G G至少

22、有两个连通分支，则称至少有两个连通分支，则称G G为为森林森林。v在无向树中，悬挂顶点称为在无向树中，悬挂顶点称为树叶树叶，度数大于或等于，度数大于或等于2 2的顶的顶点称为点称为分支点分支点。12/26/202225第十六章第十六章 树树定理定理16.116.1 设设G=G=是是n n阶阶m m条边的无向图条边的无向图,则下面各命则下面各命题是等价的：题是等价的：（1 1）G G是树。是树。（2 2）G G中任意两个顶点之间存在唯一的路径。中任意两个顶点之间存在唯一的路径。（3 3）G G中无回路且中无回路且m=n-1m=n-1。（4 4）G G是连通的且是连通的且m=n-1m=n-1。(5

23、)G(5)G是连通的且是连通的且G G中任何边均为桥。中任何边均为桥。(6)G(6)G中没有回路，但在任何两个不同的顶点之间加一条中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。新边，在所得的图中得到唯一的一个含新边的圈。12/26/202226第十六章第十六章 树树（4 4）G G是连通的且是连通的且m=n-1m=n-1。(5)G(5)G是连通的且是连通的且G G中任何边均为桥。中任何边均为桥。证明：证明：（4 4）（5 5）只需证明只需证明G中每条边均为桥中每条边均为桥.eE，均有，均有E(G-e)=n-1-1=n-2，由于，由于n阶图阶图G是连通的

24、至是连通的至少需要少需要n-1条边，所以条边，所以G-e已不是连通图，故已不是连通图，故e为桥。为桥。(5)G(5)G是连通的且是连通的且G G中任何边均为桥。中任何边均为桥。(6)G(6)G中没有回路，但在任何两个不同的顶点之间加一条中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。新边，在所得的图中得到唯一的一个含新边的圈。证明：证明：（5 5）（6 6）由于由于G中每条边均为桥，因而中每条边均为桥，因而G中无圈，又由于中无圈，又由于G连通，所连通，所以以G为树。对于为树。对于 u,vu,vV且且u v,则则u,v之间存在唯一的路径之间存在唯一的路径T

25、，则，则T（u,v）(u,v)为加的新边为加的新边)为为G中的圈，显然圈是中的圈，显然圈是唯一的。唯一的。12/26/202227第十六章第十六章 树树(6)G(6)G中没有回路，但在任何两个不同的顶点之间加一条中没有回路，但在任何两个不同的顶点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。新边，在所得的图中得到唯一的一个含新边的圈。(1)G(1)G是树。是树。证明：证明：（6 6）（1 1）只要证明只要证明G是连通的。是连通的。u,vu,vV且且u v，则新边，则新边(u,v)G产生唯一的圈产生唯一的圈C，显然有，显然有C-(u,v)为为G中中u到到v的通路，故的通路，故uv,由由u

26、,v的任意性可知，的任意性可知，G是连通的。是连通的。12/26/202228第十六章第十六章 树树定理定理16.216.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T中至少有两片树叶。中至少有两片树叶。证证：设：设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理16.1可知可知 2(n-1)=d(vi)x+2(n-x)解得解得 x 2.以上两个定理给出了无向树的主要性质，利用这以上两个定理给出了无向树的主要性质，利用这些性质和握手定理，可以画出阶数些性质和握手定理，可以画出阶数n n比较小的比较小的所有非同构的无向树。所有非同构的无向树。12/26/202229第十六章第

27、十六章 树树例例16.2 16.2 参见课本参见课本P P375375.练习练习1 1：无向树：无向树G有有5片树叶，片树叶，3个个2度分支点，其余分支度分支点，其余分支点均为点均为3度，问度，问G有多少个顶点？有多少个顶点？解：解：设设G有有n个顶点个顶点,则有下列关系式则有下列关系式 5 1+3 2+(n-5-3)3=2(n-1)解得：解得：n=11 12/26/202230第十六章第十六章 树树16.2 16.2 生成树生成树 定义定义16.2 16.2 设设T是无向图是无向图G的子图并且为树，则称的子图并且为树，则称T为为G的的树树。若若T是是G的树且为生成子图，则称的树且为生成子图，

28、则称T是是G的的生成树生成树。设设T是是G的生成树，的生成树，e eE(G),若若eE(T)，则称，则称e为为T的的树枝树枝，否则称，否则称e为为T的的弦弦。称导出子图称导出子图GE(G)-E(T)为为T的的余树余树，记作，记作T。图中，图中，红色边红色边表示生表示生成树，成树，黑色边黑色边组成其组成其余树。可见，余树可余树。可见，余树可能不连通，也可能含能不连通，也可能含回路。回路。12/26/202231第十六章第十六章 树树定义定义16.516.5 设无向连通带权图设无向连通带权图G=,T是是G的一棵的一棵生成树，生成树，T的各边权之和称为的各边权之和称为T的的权权，记作，记作W(T).

29、G的所的所有生成树中权最小的生成树称为有生成树中权最小的生成树称为G的的最小生成树最小生成树。KruskalKruskal算法算法 一种求最小生成树的算法一种求最小生成树的算法设设n阶无向连通带权图阶无向连通带权图G=有有m条边条边,不妨设不妨设G中无中无环环(否则可先删去否则可先删去)，算法为：，算法为：(1)将将m条边按权从小到大顺序排列，设为条边按权从小到大顺序排列，设为e1,e2,em。(2)取取e1在在T中，然后依次检查中，然后依次检查e2,em，若，若ej(j=2,3,m)与与T中的边不能构成回路，则取中的边不能构成回路，则取ej在在T中，中，否则放弃否则放弃ej，考虑下一条边，直

30、至，考虑下一条边，直至jm。(3)算法停止时得到的算法停止时得到的T为为G的最小生成树。的最小生成树。12/26/202232第十六章第十六章 树树例：例：用用Kruskal算法求下图的最算法求下图的最小生成树。小生成树。练习：练习：求下图的求下图的最小生成树。最小生成树。12/26/202233本讲小结本讲小结1 1、掌握欧拉图的定义、掌握欧拉图的定义2 2、掌握判断欧拉图的方法、掌握判断欧拉图的方法3 3、哈密尔顿图的定义、哈密尔顿图的定义4 4、掌握判断哈密尔顿图的方法（充分条件）、掌握判断哈密尔顿图的方法（充分条件）5 5、掌握树的定义、掌握树的定义6 6、最小生成树及其算法、最小生成树及其算法作业：作业：P304第第9题题离散数学离散数学 第第23讲讲