1、特殊图信息学院计算机应用技术系信息学院计算机应用技术系讲课教师：胡静讲课教师：胡静办公地点：信息楼办公地点：信息楼805电子邮箱：电子邮箱：ise_ 第第23讲讲1/3311/29/20241离散数学离散数学 第第2323讲讲回顾上节课内容：回顾上节课内容：l图论中基本概念图论中基本概念l握手定理及推论握手定理及推论l完全图及其特征完全图及其特征l通路及回路通路及回路？2/3311/29/20242离散数学离散数学 第第2323讲讲本讲基本知识点：本讲基本知识点：l1、欧拉图、欧拉图 欧拉图定义欧拉图定义 欧拉图判断欧拉图判断l2、哈密尔顿图、哈密尔顿图 哈密尔顿图定义哈密尔顿图定义 哈密尔顿
2、图判断充分条件哈密尔顿图判断充分条件l3、树、树 树定义树定义 最小生成树最小生成树？3/3311/29/20243 18 18世纪，在俄国哥尼斯堡城世纪，在俄国哥尼斯堡城（KonnigsbergKonnigsberg）（今俄罗斯加里宁）（今俄罗斯加里宁格勒）普莱格尔（格勒）普莱格尔（PregelPregel）河上有）河上有7 7座桥河中间有两座岛，岛与河岸座桥河中间有两座岛，岛与河岸之间架有六座桥，另一座桥则连接之间架有六座桥，另一座桥则连接着两个岛星期天散步已成为当地着两个岛星期天散步已成为当地居民一个习惯，但试图走过这么七居民一个习惯，但试图走过这么七座桥，而且每桥只走过一次却从来座桥，
3、而且每桥只走过一次却从来没有成功过直至引发瑞士数学家没有成功过直至引发瑞士数学家欧拉欧拉(Leonhard Euler(Leonhard Euler，170717071783)1783)注意之前，没有些人能够处理注意之前，没有些人能够处理这个问题这个问题第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图4/3311/29/20244第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图陆地地岛屿岛屿陆地地哥尼斯堡七哥尼斯堡七桥问题怎样不重复地走完七桥后回到起点？。A AB BC CD D5/3311/29/20245第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图15.115.1欧拉欧拉图定定义15.115
4、.1经过图经过图(无向图或有向图无向图或有向图)中全部边一次且仅一次行遍全中全部边一次且仅一次行遍全部顶点通路称为部顶点通路称为欧拉通路欧拉通路。经过图中全部边一次且仅一次行遍全部顶点回路称为经过图中全部边一次且仅一次行遍全部顶点回路称为欧欧拉回路拉回路。含有欧拉回路图称为含有欧拉回路图称为欧拉图欧拉图。含有欧拉通路而无欧拉回路图称为含有欧拉通路而无欧拉回路图称为半欧拉图半欧拉图。要求：要求：平凡平凡图是欧拉是欧拉图。6/3311/29/20246第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图定理定理15.115.1无向图无向图G G是欧拉图是欧拉图 G G是连通图，且是连通图，且G G中没有
5、奇度顶点。中没有奇度顶点。定理定理15.215.2无向图无向图G G是半欧拉图是半欧拉图 G G是连通图，且是连通图，且G G中恰有两个奇度中恰有两个奇度顶点。而且这两个奇度结点分别为欧拉通路起点和终点。顶点。而且这两个奇度结点分别为欧拉通路起点和终点。任意两点之间都有通路7/3311/29/20247解解：在在图图中中，仅仅有有两两个个度度数数为为奇奇数数结结点点b b，c c，因因而而存存在在从从b b到到c c欧欧拉拉通通路路，蚂蚂蚁蚁乙乙走走到到c c只只要要走走一一条条欧欧拉拉通通路路，边边数数为为9 9条条。而而蚂蚂蚁蚁甲甲要要想想走走完完全全部部边边抵抵达达c c，最最少少要要先
6、先走走一一条条边边抵抵达达b b，再再走走一一条条欧欧拉拉通通路路，因因而而它它最最少少要要走走1010条条边边才才能能抵抵达达c c，所以乙必胜。，所以乙必胜。例例15.1(15.1(蚂蚁比比赛问题)甲、乙两只甲、乙两只蚂蚁分分别位于右位于右图中中结点点a a，b b处，并，并设图中中边长度是相等。甲、乙度是相等。甲、乙进行比行比赛：从：从它它们所在所在结点出点出发，走，走过图中全中全部部边最最终抵达抵达结点点c c处。假如它。假如它们速度相同，速度相同，问谁先抵达目先抵达目标地？地？c cb(b(乙乙)a(a(甲甲)第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图8/3311/29/2024
7、8一笔画问题判断一笔画问题判断对于上图，有对于上图，有图图(a)(a)能一笔画而且能回到出发点，能一笔画而且能回到出发点，图图(b)(b)能一笔画但不能回到出发点。能一笔画但不能回到出发点。1 111111010(a)(a)12129 92 28 83 34 47 75 56 61 12 23 34 45 5(b)(b)第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图9/3311/29/20249求欧拉回路求欧拉回路Fleury算法算法1.1.任取任取v0Vv0V，令，令P0P0v0v0；2.2.设设P0P0v0e1v1e2eiviv0e1v1e2eivi，按下面方法从，按下面方法从E-E-e1
8、,e2,eie1,e2,ei中选取中选取ei+1ei+1：1)1)ei+1ei+1与与vivi相关联；相关联；2)2)除非无别边可选取，不然除非无别边可选取，不然ei+1ei+1不应该为不应该为GGG-G-e1,e2,eie1,e2,ei中桥；中桥；3)3)当当2 2）不能再进行时，算法结束。）不能再进行时，算法结束。第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图10/3311/29/202410例例15.2：Fleury算法应用算法应用在右图所表示欧拉图在右图所表示欧拉图中，求从中，求从v1v1出发欧拉回出发欧拉回路。路。假如假如P P4 4v v1 1e e1 1v v2 2e e2 2v
9、 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第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图11/3311/29/2024111 111111010(a)(a)12129 92 28 83 34 47 75 56 6第十五章第十五
10、章 欧拉欧拉图与哈密与哈密尔顿图桥实例桥实例12/3311/29/2024121 111111010(a)(a)12129 92 28 83 34 47 75 56 6goback第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图13/3311/29/2024131 111111010(a)(a)12129 92 28 83 34 47 75 56 6goback第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图14/3311/29/202414定理定理15.315.3有向图有向图D D是欧拉图是欧拉图 D是强连通图且每个顶点入度都等于是强连通图且每个顶点入度都等于出度。出度。定理定理15.415.4
11、有向图有向图D D是半欧拉图是半欧拉图 D是单向连通，且是单向连通，且D D中恰有两个奇中恰有两个奇度顶点，其中一个入度比出度大度顶点，其中一个入度比出度大1 1，另一个出度比入度大，另一个出度比入度大1 1，而其余顶点入度都等于出度。，而其余顶点入度都等于出度。第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图15/3311/29/202415第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图答案：图答案：图a a和图和图d d是欧拉图；图是欧拉图；图b b和图和图e e不是欧拉图，但存不是欧拉图，但存在欧拉通路；图在欧拉通路；图c c和图和图f f不存在欧拉通路。不存在欧拉通路。练习：判断以下各图
12、是不是欧拉图或半欧拉图。练习：判断以下各图是不是欧拉图或半欧拉图。16/3311/29/202416哈密哈密尔顿图起源：起源：-周游世界周游世界问题18591859年，数学家哈密尔顿创造了一个游戏：他把一个正十二年，数学家哈密尔顿创造了一个游戏：他把一个正十二面体二十个顶点分别标上了世界上二十大城市名字，把正十面体二十个顶点分别标上了世界上二十大城市名字，把正十二面体三十条棱解释成连接这些城市之间交通线。玩法是从二面体三十条棱解释成连接这些城市之间交通线。玩法是从某个城市（顶点）出发，沿着这些交通线（边）行走，要求某个城市（顶点）出发，沿着这些交通线（边）行走，要求经过每个城市恰好一次，然后回
13、到出发点。他把这个游戏称经过每个城市恰好一次，然后回到出发点。他把这个游戏称为为“周游世界周游世界”。1 12 23 34 45 56 67 78 89 910101111121213131414151516161717181819192020第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图17/3311/29/202417第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图15.2 15.2 哈密尔顿图哈密尔顿图定义定义15.2 15.2 v经过图（有向图或无向图）中全部顶点一次且仅一次通路称为经过图（有向图或无向图）中全部顶点一次且仅一次通路称为哈密尔顿通路哈密尔顿通路。v经过图中全部顶点一次且仅
14、一次回路称为经过图中全部顶点一次且仅一次回路称为哈密尔顿回路哈密尔顿回路。v含有哈密顿回路图称为含有哈密顿回路图称为哈密尔顿图哈密尔顿图.v含有哈密顿通路但不含有哈密顿回路图称为含有哈密顿通路但不含有哈密顿回路图称为半哈密尔顿图半哈密尔顿图.要求要求:平凡图是哈密尔顿图。平凡图是哈密尔顿图。18/3311/29/202418第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图定理定理15.715.7：设设G G是是n n阶无向简单图，若对阶无向简单图，若对G G中任意不相邻顶点中任意不相邻顶点u ui i,u,uj j，都有都有 d(u d(ui i)+d(u)+d(uj j)n-1 )n-1 则则
15、G G中存在哈密尔顿通路中存在哈密尔顿通路.推推论 设设G G为为n(n 3)n(n 3)阶无向简单图，若对于阶无向简单图，若对于G G中任意两个不中任意两个不相邻顶点相邻顶点u ui i,u,uj j，均有均有 d(u d(ui i)+d(u)+d(uj j)n)n 则则G G中存在哈密顿回路，从而中存在哈密顿回路，从而G G为哈密尔顿图。为哈密尔顿图。无向无向图含有哈密含有哈密尔顿路与回路充分条件路与回路充分条件19/3311/29/202419利用哈密利用哈密尔顿图处理理实际问题经典例典例题1 1：某地有某地有5 5个风景点，若每个风景点个风景点，若每个风景点都有两条道路与其它点相通。问
16、游人可否经过每都有两条道路与其它点相通。问游人可否经过每个风景点恰好一次而游完这个风景点恰好一次而游完这5 5处？处？解解将将5 5个风景点看成是有个风景点看成是有5 5个结点无向图，两风景个结点无向图，两风景点间道路看成是无向图边，因为每处都有两条道点间道路看成是无向图边，因为每处都有两条道路与其它结点相通，故每个结点度数均为路与其它结点相通，故每个结点度数均为2 2，从而，从而任意两个不相邻结点度数之和等于任意两个不相邻结点度数之和等于4 4，恰好为总结，恰好为总结点数减点数减1 1。故此图中存在一条哈密尔顿通路，所以。故此图中存在一条哈密尔顿通路，所以本题有解。本题有解。第十五章第十五章
17、 欧拉欧拉图与哈密与哈密尔顿图20/3311/29/202420第十五章第十五章 欧拉欧拉图与哈密与哈密顿图经典例典例题2 2：在某次国际会议预备会中，共有在某次国际会议预备会中，共有8 8人参加，人参加，他们来自不一样国家，已知他们中任何两个无共同语言人他们来自不一样国家，已知他们中任何两个无共同语言人中每一个，与其余有共同语言人数之和大于或等于中每一个，与其余有共同语言人数之和大于或等于8 8，问能，问能否将这否将这8 8个人排在圆桌旁，使其任何人都能与两边人交谈。个人排在圆桌旁，使其任何人都能与两边人交谈。解解 以以8 8个人分别为无向简单图个人分别为无向简单图G G顶点，若任意两人顶点
18、，若任意两人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有共同语言人数。由已知条件可有共同语言人数。由已知条件可知，任意与知，任意与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中存在哈密顿回路，按寻找到回路中存在哈密顿回路，按寻找到回路次序安排座次即可。次序安排座次即可。21/3311/2
19、9/202421经典例典例题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）d d会讲日语和汉语会讲日语和汉语5 5）e e会讲德语和意大利语会讲德语和意大利语6 6）f f会讲法语、日语和俄语会讲法语、日语和俄语7 7）g g会讲法语和德语会讲法语和德语试问这试问这7 7个人应怎样安排座位，才能使每个人和他身边人交个人应怎样安排座位，才能使每个人和他身边人交谈？谈？第十五章第十五章 欧拉欧拉图
20、与哈密与哈密尔顿图22/3311/29/202422解：设无向图解：设无向图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有共同语言有共同语言。如右图为连通图，将七人排座围圆桌而坐，使得每个人都如右图为连通图，将七人排座围圆桌而坐，使得每个人都能与两边交谈。即在右图中寻找一条哈密尔顿回路，能与两边交谈。即在右图中寻找一条哈密尔顿回路，第十五章第十五章 欧拉欧拉图与哈密与哈密尔顿图fgecabd经观察该回路是经观察该回路是abdfgecaabdfgeca23/3311/29/2024
21、23第十六章第十六章 树16.116.1无向无向树及其性及其性质定定义16.116.1v连通无回路无向图称为连通无回路无向图称为无向树无向树，简称，简称树树,惯用惯用T T表示树。表示树。v平凡图称为平凡图称为平凡树。平凡树。v若无向图若无向图G G最少有两个连通分支，则称最少有两个连通分支，则称G G为为森林森林。v在无向树中，悬挂顶点称为在无向树中，悬挂顶点称为树叶树叶，度数大于或等于，度数大于或等于2 2顶点顶点称为称为分支点分支点。24/3311/29/202424第十六章第十六章 树定理定理16.116.1 设设G=G=是是n n阶阶m m条边无向图条边无向图,则下面各命题则下面各命
22、题是等价：是等价：（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)G(5)G是连通且是连通且G G中任何边均为桥。中任何边均为桥。(6)G(6)G中没有回路，但在任何两个不一样顶点之间加一条中没有回路，但在任何两个不一样顶点之间加一条新边，在所得图中得到唯一一个含新边圈。新边，在所得图中得到唯一一个含新边圈。25/3311/29/202425第十六章第十六章 树（4 4）G G是连通且是连通且m=n-1m=n-1。(5
23、)G(5)G是连通且是连通且G G中任何边均为桥。中任何边均为桥。证实：（4 4）（5 5）只需证实只需证实G中每条边均为桥中每条边均为桥.eE，都有，都有E(G-e)=n-1-1=n-2，因为，因为n阶图阶图G是连通最少是连通最少需要需要n-1条边，所以条边，所以G-e已不是连通图，故已不是连通图，故e为桥。为桥。(5)G(5)G是连通且是连通且G G中任何边均为桥。中任何边均为桥。(6)G(6)G中没有回路，但在任何两个不一样顶点之间加一条中没有回路，但在任何两个不一样顶点之间加一条新边，在所得图中得到唯一一个含新边圈。新边，在所得图中得到唯一一个含新边圈。证实：（5 5）（6 6）因为因
24、为G中每条边均为桥，因而中每条边均为桥，因而G中无圈，又因为中无圈，又因为G连通，所连通，所以以G为树。对于为树。对于 u,vu,vV且且u v,则则u,v之间存在唯一路径之间存在唯一路径T，则，则T（u,v）(u,v)为加新边为加新边)为为G中圈，显然圈是唯一。中圈，显然圈是唯一。26/3311/29/202426第十六章第十六章 树(6)G(6)G中没有回路，但在任何两个不一样顶点之间加一条中没有回路，但在任何两个不一样顶点之间加一条新边，在所得图中得到唯一一个含新边圈。新边，在所得图中得到唯一一个含新边圈。(1)G(1)G是树。是树。证实：（6 6）（1 1）只要证实只要证实G是连通。是
25、连通。u,vu,vV且且u v，则新边，则新边(u,v)G产生唯一圈产生唯一圈C，显然有，显然有C-(u,v)为为G中中u到到v通路，故通路，故uv,由由u,v任意性可知，任意性可知，G是连通。是连通。27/3311/29/202427第十六章第十六章 树定理定理16.216.2 设设T是是n阶非平凡无向树，则阶非平凡无向树，则T中最少有两片树叶。中最少有两片树叶。证：设：设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理16.1可知可知 2(n-1)=d(vi)x+2(n-x)解得解得 x 2.以上两个定理给出了无向树主要性质，利用这些以上两个定理给出了无向树主要性质，利用这些性质和
26、握手定理，能够画出阶数性质和握手定理，能够画出阶数n n比较小全部比较小全部非同构无向树。非同构无向树。28/3311/29/202428第十六章第十六章 树例例16.216.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 29/3311/29/202429第十六章第十六章 树16.216.2生成生成树 定定义16.216.2设设
27、T是无向图是无向图G子图而且为树，则称子图而且为树，则称T为为G树树。若若T是是G树且为生成子图，则称树且为生成子图，则称T是是G生成树生成树。设设T是是G生成树，生成树，e eE(G),若若eE(T)，则称，则称e为为T树树枝枝，不然称，不然称e为为T弦弦。称导出子图称导出子图GE(G)-E(T)为为T余树余树，记作，记作T。图中，图中，红色边红色边表示生表示生成树，成树，黑色边黑色边组成其组成其余树。可见，余树可余树。可见，余树可能不连通，也可能含能不连通，也可能含回路。回路。30/3311/29/202430第十六章第十六章 树定定义16.516.5 设无向连通带权图设无向连通带权图G=
28、,T是是G一棵生一棵生成树，成树，T各边权之和称为各边权之和称为T权权，记作，记作W(T).G全部生成树全部生成树中权最小生成树称为中权最小生成树称为G最小生成树最小生成树。KruskalKruskal算法算法一个求最小生成树算法一个求最小生成树算法设设n阶无向连通带权图阶无向连通带权图G=有有m条边条边,不妨设不妨设G中无中无环环(不然可先删去不然可先删去)，算法为：，算法为：(1)将将m条边按权从小到大次序排列，设为条边按权从小到大次序排列，设为e1,e2,em。(2)取取e1在在T中，然后依次检验中，然后依次检验e2,em，若，若ej(j=2,3,m)与与T中边不能组成回路，则取中边不能
29、组成回路，则取ej在在T中，不然放弃中，不然放弃ej，考虑下一条边，直至，考虑下一条边，直至jm。(3)算法停顿时得到算法停顿时得到T为为G最小生成树。最小生成树。31/3311/29/202431第十六章第十六章 树例：例：用用Kruskal算法求下列图最算法求下列图最小生成树。小生成树。2 21 12 21 13 34 43 31 15 51 11 13 31 1。OK!。2 21 14 45 51 15 55 54 45 53 33 32 2练习：求下列图求下列图最小生成树。最小生成树。32/3311/29/202432本本讲小小结1 1、掌握欧拉、掌握欧拉图定定义2 2、掌握判断欧拉、掌握判断欧拉图方法方法3 3、哈密、哈密尔顿图定定义4 4、掌握判断哈密、掌握判断哈密尔顿图方法（充分条件）方法（充分条件）5 5、掌握、掌握树定定义6 6、最小生成、最小生成树及其算法及其算法作业：作业：P304第第9题题离散数学离散数学 第第23讲讲33/3311/29/202433
