第7章 特殊图-《离散数学（微课版）》教学课件

《离散数学》第7章特殊图内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.8本章导读本章介绍几种特殊的图：树欧拉图哈密顿图偶图平面图重点1无向树的基本概念2无向树的性质，特别是m＝n－1和至少2个叶结点3生成树与最小生成树及其求解算法4

根树的概念与分类5欧拉图及其判定，Fleury算法6

哈密顿图及其判定7

偶图及其判定，匹配8平面图及其判定，欧拉公式，库拉托夫斯基定理难点1

哈密顿图的判定2

平面图的判定3

库拉托夫斯基定理学习要求内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.8哈密顿自幼聪明，被称为神童。3岁能读英语，会算术；5岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；9岁便熟悉了波斯语、阿拉伯语和印地语。他自幼喜欢算术，计算很快。1818年遇到美国“计算神童”Z．科耳本（Colburn）后对数学产生了更深厚的兴趣。到1820年已阅读了牛顿的《自然哲学的数学原理》，并对天文学有强烈爱好，常用自己的望远镜观测天体。威廉·哈密顿爱尔兰数学家、物理学家、力学家哈密顿1820年开始读P．S．拉普拉斯（Laplace）的著作《天体力学》，1822年指出了此书中的一个错误；同年他开始进行科学研究工作，对曲线和曲面的性质进行了系列研究，并用于几何光学。爱尔兰科学院院士R．J．布林克莱（Brinkley）称他是“这个年龄（17岁）的第一数学家”。首先建立了光学的数学理论，并把这种理论移植到动力学中去，提出了著名的“哈密顿最小作用原理”，即用一个变分式推出各种动力学定律。还把广义坐标和广义动量作为典型变量来建立动力学方程──哈密顿典型方程。威廉·哈密顿爱尔兰数学家、物理学家、力学家哈密顿还建立了与系统的总能量有关的哈密顿函数，这些工作推动了变分法和微分方程理论的进一步研究。哈密顿方程是一个经典力学方程。哈密顿函数既是经典物理学中的一个函数，也是量子物理学中的一个算子。哈密顿图是图论中的一个术语。他也喜欢文学，成为数学大师后，仍不断赋诗填词，一直认为文学与数学是近似的学科——都是抽象思维的文字与符号。他曾写道：“诗与数学是近亲。”威廉·哈密顿爱尔兰数学家、物理学家、力学家哈夫曼他从小聪慧好学，在俄亥俄州立大学毕业时只有17岁。然后他进入麻省理工学院（MIT）一边工作，一边深造，哈夫曼编码就是他在1952年做博士论文时发明的。这是一种根据字母的使用频率而设计的变长码，能大大提高信息的传输效率，至今仍有广泛的应用。在MIT一直工作到1967年。之后转入加州大学的圣克鲁兹分校，成为该校计算机科学系的创始人，并于1970年至1973年任系主任，为此系的学术研究做出了许多杰出贡献。1994年哈夫曼退休。戴维·哈夫曼美国计算机科学家哈夫曼除了哈夫曼编码外，哈夫曼在其他方面也有不少创造，他设计的二叉最优搜索树算法就被认为是同类算法中效率最高的，因而被命名为哈夫曼算法，是动态规划（DynamicProgramming）的一个范例。哈夫曼算法也广泛应用于传真机、图像压缩和计算机安全领域。但他却从未为此算法申请过专利或其他能够为他带来经济利益的东西，而是将全部的精力放在教学上，用他自己的话来说，“我所要给世界带来的就是我的学生。”戴维·哈夫曼美国计算机科学家哈夫曼1982年获得美国电气与电子工程师学会（IEEE）计算机先驱奖。1973年获得IEEE的麦克道尔（McDowell）奖。1998年IEEE下属的信息论分会为纪念信息论创立50周年，授予他金禧（GoldenJubilee）奖。1999年6月，荣获了以哈明码发明人命名的哈明奖章（HammingMedal）。戴维·哈夫曼美国计算机科学家管梅谷1957年毕业于华东师范大学数学系1957年至1990年在山东师范大学工作1984年至1990年担任山东师范大学校长1990年至1995年任复旦大学运筹学系主任一直从事运筹学、组合优化与图论方面的研究工作，是国内外知名度很高的学者。代表性论著有《线性规划》《图论中的几个极值问题》《奇偶点图上作业法》等。1960年在国际上最先提出的邮递员问题被国际图论界命名为“中国邮路问题”，载入经典著作。2016年，被中国运筹学会授予科学技术奖——终身成就奖。管梅谷上海市人数学家内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.8引言树是图论中的一个非常重要的概念，而在计算机科学中有着非常广泛的应用，例如现代计算机操作系统均采用树形结构来组织文件和文件夹，本章介绍树的基本知识和应用。在本章中，所谈到的图都假定是简单图；所谈到的回路均指简单回路或基本回路。并且同一个图形表示的回路(简单的或基本的)，可能有不同的交替序列表示方法，但我们规定它们表示的是同一条回路。7.1.1树的基本概念及性质例7.12018年俄罗斯世界杯8强的比赛结果图，最后胜利的队捧得大力神杯。英格兰瑞典俄罗斯克罗地亚巴西比利时乌拉圭法国英格兰克罗地亚比利时法国克罗地亚法国法国定义7.1连通而不含回路的无向图称为无向树(UndirectedTree)，简称树(Tree)，常用T表示树。树中度数为1的结点称为叶(Leaf)；度数大于1的结点称为分支点(BranchPoint)或内部结点(InteriorPoint)。每个连通分支都是树的无向图称为森林(Forest)。平凡图称为平凡树(TrivialTree)。不含回路的无向图称为森林树中没有环和平行边，因此一定是简单图在任何非平凡树中，都无度数为0的结点解题小贴士——无向图G是树的判断（1）图G是连通的。（2）图G中不存在回路。例10.2.2判断下图中的图哪些是树？为什么？(a)(b)(c)(d)树树不是树森林不是树连通，无回路连通，无回路不连通有回路，无回路不是森林树的性质定理10.2.1设无向图G=<V,E>，|V|=n，|E|=m，下列各命题是等价的：G连通而不含回路(即G是树)G中无回路，且m=n-1G是连通的，且m=n-1G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路G是连通的，但删除G中任一条边后，便不连通(n≥2)G中每一对结点之间有惟一一条基本通路(n≥2)证明①②：对n作归纳。n=1时，m=0，显然有m=n-1。假设n=k时命题成立，现证n=k+1时也成立。由于G连通而无回路，所以G中至少有一个度数为1的结点v0，在G中删去v0及其关联的边，便得到k个结点的连通而无回路的图，由归纳假设知它有k-1条边。再将结点v0及其关联的边加回得到原图G，所以G中含有k+1个结点和k条边，符合公式m=n-1。所以，G中无回路，且m=n-1。G连通而不含回路(即G是树)G中无回路，且m=n-1；②③：设G有k个连通分支G1，G2，…，Gk，其结点数分别为n1，n2，…，nk，边数分别为m1，m2，…，mk，且，由于G中无回路，所以每个Gi(i=1,2,…,k)均为树，因此mi=ni–1（i=1,2,…,k），于是故k=1，所以G是连通的，且m=n-1。G中无回路，且m=n-1；G是连通的，且m=n-1；③④：首先证明G中无回路。对n作归纳。n=1时，m=n-1=0，显然无回路。假设结点数n=k-1时无回路，下面考虑结点数n=k的情况。因G连通，故G中每一个结点的度数均大于等于1。可以证明至少有一个结点v0，使得deg(v0)=1，因若k个结点的度数都大于等于2，则从而m≥k，即至少有k条边，但这与m=n-1矛盾。G是连通的，且m=n-1；G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路；③④：在G中删去v0及其关联的边，得到新图G’，根据归纳假设知G’无回路，所以再将结点v0及其关联的边加回得到原图G，则G也无回路。其次证明在G中任二结点vi，vj之间增加一条边(vi,vj)，得到一条且仅一条基本回路。由于G是连通的，从vi到vj有一条通路L，再在L中增加一条边(vi,vj)，就构成一条回路。若此回路不是惟一和基本的，则删去此新边，G中必有回路，得出矛盾。由于deg(v0)=1，④⑤：若G不连通，则存在两结点vi和vj，在vi和vj之间无通路，此时增加边(vi,vj)，不会产生回路，但这与题设矛盾。由于G无回路，所以删去任一边，图便不连通。G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路；G是连通的，但删除G中任一条边后，便不连通；(n≥2)G是连通的，但删除G中任一条边后，便不连通；(n≥2)G中每一对结点之间有惟一一条基本通路。(n≥2)⑤⑥：由于G是连通的，因此G中任二结点之间都有通路，于是有一条基本通路。若此基本通路不惟一，则G中含有回路，删去回路上的一条边，G仍连通，这与题设不符。所以此基本通路是惟一的。⑥①：显然G是连通的。若G中含回路，则回路上任二结点之间有两条基本通路，这与题设矛盾。因此，G连通且不含回路。G中每一对结点之间有惟一一条基本通路

(n≥2)G连通而不含回路(即G是树)树的特点在结点给定的无向图中，树是边数最多的无回路图树是边数最少的连通图由此可知，在无向图G=(n,m)中，若m＜n-1，则G是不连通的若m＞n-1，则G必含回路由定理7.1(4)：G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路。由定理7.1(5)：G是连通的，但删除G中任一条边后，便不连通。定理7.2任意非平凡树T=(n,m)都至少有两片叶。证明因非平凡树T是连通的，从而T中各结点的度数均大于等于1。设T中有k个度数为1的结点(即k片叶)，其余的结点度数均大于等于2。由握手定理得由于树中有m=n-1，因此可得k≥2，

于是2(n-1)≥2n-k，这说明T中至少有两片叶。平凡树有多少片叶07..2生成树及算法定义7.2给定图G=<V,E>，若G的某个生成子图是树，则称之为G的生成树(SpanningTree)，记为TG。生成树TG中的边称为树枝(Branch)G中不在TG中的边称为弦(Chord)TG的所有弦的集合称为生成树的补(Complement)

解题小贴士——图G'是图G的生成树的判断（1）图G'是图G的生成子图。（2）图G'是树。例7.3判断下图中的图(b)、(c)、(d)、(e)是否是图(a)的生成树。abcdef(a)abcdef(b)abcdef(c)abcdef(d)bcdef(e)不是是不是不是树枝：(a,c)、(a,d)、(b,f)、(c,f)、(c,e)弦：(a,b)、(b,c)、(c,d)、(d,e)、(e,f)定理7.3一个图G=<V,E>存在生成树TG=<V,ET>的充分必要条件是G是连通的。证明

必要性：假设TG=<V,ET>是G=<V,E>的生成树，由定义10.2.1，TG是连通的，于是G也是连通的。充分性：假设G=<V,E>是连通的。如果G中存在回路C1，可删除C1中一条边得到图G1，它仍连通且与G有相同的结点集。如果G1中无回路，G1就是生成树。如果G1仍存在回路C2，可删除C2中一条边，如此继续，直到得到一个无回路的连通图H为止。因此，H是G的生成树。如果G中无回路，G本身就是生成树。

说明一个无向连通图G，如果G是树，则它的生成树是唯一的，就是G本身。如果G不是树，那么它的生成树就不唯一了。定理7.3的证明过程就给出了求连通图G＝(n,m)的生成树的一种算法，称为“破圈法”，算法的关键是判断G中是否有回路。若有回路，则删除回路中的一条边，直到剩下的图中无回路为止，由定理7.1知，共删除m-n+1条边。由定理7.3和定理7.1，连通图G＝(n,m)一定存在生成树，且其有n个结点，n-1条树枝，m-n+1条弦，因此选择G中不构成任何回路的n-1条边，就得到G的生成树，这种方法称为“避圈法”。

破圈法与避圈法算法7.1

求连通图G=<V,E>的生成树的破圈法：每次删除回路中的一条边，其删除的边的总数为m-n+1。算法7.2

求连通图G=<V,E>的生成树的避圈法：每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。由于删除回路上的边和选择不构成任何回路的边有多种选法，所以产生的生成树不是惟一的。解题小贴士——求连通图G＝(n,m)的生成树使用破圈法：找出一条回路，并删除该回路中的一条边，直到图中没有回路为止，删除的边的总数为m-n+1。使用避圈法：选取一条边，验证该边与已选取的边不构成回路，选取的边的总数为n-1。例7.4用破圈法生成树由于n=6，m=9，所以m-n+1=4，故要删除的边数为4，因此只需4步即可。123456用避圈法求生成树由于n=6，所以n-1=5，故要选取5条边，因此需5步即可。123456123456说明由于生成树的形式不惟一，故上述两棵生成树都是所求的。破圈法和避圈法的计算量较大，主要是需要找出回路或验证不存在回路。算法7.3求连通图G=<V,E>的生成树的广度优先搜索算法：任选s∈V，将s标记为0，令L={s}，V=V-{s}，k=0；如果V=Φ，则转④，否则令k=k+1；依次对L中所有标记为k-1的结点v，如果它与V中的结点w相邻接，则将w标记为k，指定v为w的前驱，令L=L∪{w}，V=V-{w}，转②；EG={(v,w)|w∈L-{s}，v为w的前驱}，结束。解题小贴士——使用广度优先搜索算法求生成树使用算法7.3，从任意结点开始，逐步搜索，完成对所有节点的标记，所有结点与其前驱连接的边即为该生成树的弦。if例7.50(-)1(a)1(a)2(c)2(b)3(e)3(e)3(e)4(d)4(h)bacdgjifeh0(-)1(a)1(a)2(c)2(b)3(e)3(f)3(e)4(h)4(h)bacdgjeh用广度优先搜索算法求生成树最小生成树定义10.2.3设G=<V,E>是连通的赋权图，T是G的一棵生成树，T的每个树枝所赋权值之和称为T的权(Weight)，记为w(T)。G中具有最小权的生成树称为G的最小生成树(MinimalSpanningTree)。

一个无向图的生成树不是惟一的，同样地，一个赋权图的最小生成树也不一定是惟一的。算法7.4Kruskal算法在G中选取最小权边e1，置i=1。当i=n-1时，结束，否则转③。设已选取的边为e1,e2,…,ei，在G中选取不同于e1,e2,…,ei的边ei+1，使{e1,e2,…,ei,ei+1}中无回路且ei+1是满足此条件的最小权边。置i=i+1，转②。要点：在与已选取的边不构成回路的边中选取最小者。

解题小贴士——使用Kruskal算法求最小生成树按照边的权值从小到大逐步搜索，选取那些与已选取边不构成回路的边加入即可，共放入n-1条边。注：在算法的步骤①和③中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。例7.6用Kruskal算法求图中赋权图的最小生成树。解n=12，按算法要执行n-1=11次，w(T)=36。4655761f923adbcimjkehg343446587582451f23adbcimjkehg343452算法7.5Prim算法（1）在G中任意选取一个结点v1，置VT={v1},ET=Φ，k=1；（2）在V-VT中选取与某个vi∈VT邻接的结点vj，使得边(vi,vj)的权最小，置VT=VT∪{vj},ET=ET∪{(vi,vj)}，k=k+1；（3）重复步骤(2)，直到k=|V|。要点：从任意结点开始，每次增加一条最小权边构成一棵新树。解题小贴士——使用Prim算法求最小生成树从平凡树开始逐步搜索，每次选取与该树的结点关联的树外的最小权边构成一棵新树，共执行n-1次。注：在算法的步骤(2)中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。例7.7用Prim算法求图中赋权图的最小生成树。解n=7，按算法要执行n-1=6次，w(T)=25。5f102dbce7g64582a5f2dbce7g452a由Prim算法可以看出，每一步得到的图一定是树，故不需要验证是否有回路，因此它的计算工作量较Kruskal算法要小。

内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.87.2.1根树的定义与分类定义10.3.1一个有向图，若略去所有有向边的方向所得到的无向图是一棵树，则这个有向图称为有向树(DirectedTree)。解题小贴士——有向树的判断（1）将所有有向边都略去方向变为无向边，得到一个无向图。（2）判断该无向图是否是树。例7.8判断下图中的图哪些是有向树？为什么？(a)(c)(e)(d)(b)不是有向树不是有向树有向树有向树有向树一棵非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称之为根树(RootTree)或外向树(OutwardTree)。

入度为0的结点称为根(Root)；出度为0的结点称为叶(Leaf)；入度为1，出度大于0的结点称为内点(InteriorPoint)；又将内点和根统称为分支点(BranchPoint)。在根树中，从根到任一结点v的通路长度，称为该结点的层数(LayerNumber)；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高(Height)。定义7.5解题小贴士——根树的判断（1）判断是否为有向树。（2）计算所有结点的度数，看是否恰有一个结点的入度为0，其余所有结点的入度均为1。例7.9判断下图所示的图是否是根树？若是根树，给出其根、叶和内点，计算所有结点所在的层数和高。是根树根：v1叶：v5,v6,v8,v9,v10,v12,v13内点：v2,v3,v4,v7,v11倒置法

v1v2v3v4v5v6v7v8v9v10v11v12v13v1处在第零层，层数为0v2,v3,v4同处在第一层，层数为1v5,v6,v7,v8,v9同处在第二层，层数为2v10,v11,v12同处在第三层，层数为3v13处在第四层，层数为4这棵树的高为4v1v2v3v4v5v6v7v8v9v10v11v12v13家族关系——根树定义7.6在根树中，若从结点vi到vj可达，则称vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；若<vi,vj>是根树中的有向边，则称vi是vj的父亲(Father)，vj是vi的儿子(Son)；如果两个结点是同一个结点的儿子，则称这两个结点是兄弟(Brother)。定义7.7如果在根树中规定了每一层上结点的次序，这样的根树称为有序树(OrderedTree)。一般地，在有序树中同一层中结点的次序为从左至右。有时也可以用边的次序来代替结点的次序。k元树定义7.8设T为根树。（1）若T的每个分支点至多有k个儿子，则称T为k元树（或k叉树）（k-aryTree）；（2）若T的每个分支点都恰有k个儿子，则称T为完全k元树（Completek-aryTree）；（3）若T是k元完全树且每个叶结点的层数均为树高，则称T为满k元树（Fullk-aryTree）；（4）若k元树T是有序的，则称T为有序k元树（Orderedk-aryTree）；（5）若k元完全树T是有序的，则称T为有序完全k元树（OrderedCompletek-aryTree）；（6）若T是满k元树且是有序的，则称T为有序满k元树（FullOrderedk-aryCompleteTree）。通常，k元树至少要有一个分支点有k个儿子。注：有些书中k叉树专指k元有序树完全k元树又称为k元完全树，k叉正则树满k元树又称为k叉完全正则树子树在根树T中，任一结点v及其所有后代导出的子图T’称为T的以v为根的子树(Subtree)。当然，T’也可以有自己的子树。有序2元树的每个结点v至多有两个儿子，分别称为v的左儿子(LeftSon)和右儿子(RightSon)。有序2元树的每个结点v至多有两棵子树，分别称为v的左子树(LeftSubtree)和右子树(RightSubtree)。注意区分以v为根的子树和v的左(右)子树，v为根的子树包含v，而v的左(右)子树不包含v。解题小贴士——k元树的判断必须是根树计算所有分支点的儿子数每个分支点至多有k（包含k）个儿子即为k元树每个分支点都恰有k个儿子即为完全k元树每个分支点都恰有k个儿子且每个叶结点的层数均相同即为满k元树例7.10判断下图所示的几棵根树是什么树？2元完全树

3元树

3元完全树

3元有序完全树(b)(c)(a)122(d)133213k元完全树中分支点与叶结点数目之间的关系定理7.4在k元完全树中，若叶数为t，分支点数为i，则有：(k-1)×i=t-1证明由假设知，该树有i+t个结点。由定理7.1知，该树的边数为i+t-1。由握手定理知，所有结点的出度之和等于边数。而根据k元完全树的定义知，所有分支点的出度为k×i。因此有k×i=i+t-1即 (k-1)×i=t-1例7.11假设有一台计算机，它有一条加法指令，可计算4个数的和。如果要求16个数x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16之和，问至少要执行几次加法指令？解用4个结点表示4个数，将表示4个数之和的结点作为它们的父结点。这样本问题可理解为求一个完全4元树的分支点问题。把16个数看成叶。由定理7.4知，有(4-1)i=16-1，得i=5。所以至少要执行5次加法指令。例7.11两种可能的顺序：（a）x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16（b）x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16例7.12——一题多解设T为任意一棵完全2元树，m为边数，t为叶数（t≥2），试证明：m＝2t－2证明方法一：设T中的结点数为n，分支点数为i。根据完全2元树的定义，容易知道下面等式均成立：n＝i＋t，m＝2i，m＝n－1解关于m、n、i的三元一次方程组得m＝2t－2。方法二：在完全2元树中，除叶外，每个结点的出度均为2；除根结点外，每个结点的入度均为1。设T中的结点数为n，由握手定理可知2m＝＝2(n－t)＋n－1＝3n－2t－1＝3(m＋1)－2t－1故

m＝2t－2

＝

＋方法三：对树叶数t作归纳法。当t=2时，结点数为3，边数m=2，故m=2t-2成立。假设t=k（k≥2）时，结论成立，下面证明t=k+1时结论也成立。由于T是完全2元树，因此T中一定存在都是树叶的两个兄弟结点v1,v2，设v是v1,v2的父亲。在T中删除v1,v2，得树T’，T’仍为完全2元树，这时结点v成为树叶，树叶数t’=t-2+1=k+1-1=k，边数m’=m-2，由归纳假设知，m’=2t’-2。所以m-2=2(t-2+1)-2，故m=2t-2。方法四：对分支点数i作归纳法。当i=1时，边数m=2，树叶数t=2，故m=2t-2成立。假设i=k(k≥1)时，结论成立，下面证明i=k+1时结论也成立。由于T是完全2元树，因此T中一定存在两个儿子都是树叶的分支点，设v就是这样一个分支点，设它的两个儿子为v1,v2

。在T中删除v1,v2，得树T’，T’仍为完全2元树，这时结点v成为树叶，分支点数i’=i-1=k+1-1=k，树叶数t’=t-2+1，边数m’=m-2，由归纳假设知，m’=2t’-2。所以m-2=2(t-2+1)-2，故m=2t-2。7.2.2根树的遍历对于根树，一个十分重要的问题是要找到一些方法，能系统地访问树的结点，使得每个结点恰好访问一次，这就是根树的遍历(Ergode)问题。k元树中，应用最广泛的是2元树。由于2元树在计算机中最易处理，下面先介绍二元树的3种常用的遍历方法，然后再介绍将任意根树转化为二元树。2元树的3种常用遍历方法算法7.62元树的先根次序遍历算法：访问根按先根次序遍历根的左子树按先根次序遍历根的右子树算法7.82元树的后根次序遍历算法按后根次序遍历根的左子树按后根次序遍历根的右子树访问根算法7.72元树的中根次序遍历算法：按中根次序遍历根的左子树访问根按中根次序遍历根的右子树解题小贴士——2元树的遍历按照根、左子树、右子树的不同次序，有3种不同的遍历方法，注意对左子树、右子树的遍历顺序都是一致的。例7.13写出对图中2元树的3种遍历方法得到的结果。abedghklmicjf解先根遍历次序为abdghceijklmf中根遍历次序为gdhbaielkmjcf后根遍历次序为ghdbilmkjefca按遍历方法容易写出，只要先将该树分解为根、左子树、右子树三部分，然后再对子树作分解，直到叶为止。算法7.9根树转化为二元树算法：从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线。兄弟间用从左向右的有向边连接。按如下方法确定2元树中结点的左儿子和右儿子：直接位于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依此类推。解题小贴士——根树转化为2元树从根开始，只保留最左边儿子，相邻的弟弟变为右儿子。例7.14将下图转化为一棵二元树。v1v2v3v4v5v6v7v10v11v9v1v2v3v4v5v6v7v8v10v11v9v1v2v3v4v5v6v7v8v10v11v9反过来，也可以还原。要点：右儿子变弟弟算法7.10有序森林转化为二元树算法：先把森林中的每一棵树都表示成2元树；除第一棵2元树外，依次将剩下的每棵2元树作为左边2元树的根的右子树，直到所有的二元树都连成一棵二元树为止。解题小贴士——森林转化为2元树先把森林中的每一棵树都表示成2元树，然后从右往左，依次将每棵2元树变为左边2元树根的右子树。例7.15将图所示的森林转化成一棵二元树。v1v2v3v4v5v6v7v12v9v10v8v11v13v14v1v2v3v4v5v6v7v12v9v10v8v11v13v14将二元树转化为森林，要点是“先将根的右子树变为新二元树，再将这些二元树还原为根树”。

7.2.3最优树与哈夫曼算法在计算机及通讯事业中，常用二进制编码来表示符号，称之为码字(codeword)。例如，可用00、01、10、11分别表示字母A、B、C、D。如果字母A、B、C、D出现的频率是一样的，传输100个字母用200个二进制位。但实际上字母出现的频率很不一样，如A出现的频率为50％，B出现的频率为25％，C出现的频率为20％，D出现的频率为5％。能否用不等长的二进制序列表示字母A、B、C、D，使传输的信息的二进制位尽可能少呢？事实上，可用000表示字母D，用001表示字母C，01表示B，1表示A。这样表示，传输100个字母所用的二进制位为3×5+3×20+2×25+1×50=175。这种表示比用等长的二进制序列表示法好，节省了二进制位。但当我们用1表示A，用00表示B，用001表示C，用000表示D时，如果接收到的信息为001000，则无法辨别它是CD还是BAD。因而，不能用这种二进制序列表示A、B、C、D，要寻找另外的表示法。定义7.9设a1a2…an-1an为长度为n的符号串，称其子串a1，a1a2，…,a1a2…an-1分别为a1a2…an-1an的长度为1、2、…、n-1的前缀（Prefix）。设A={b1,b2,…,bm}是一个符号串集合，若对任意bi,bj∈A，bi≠bj，bi不是bj的前缀，bj也不是bi的前缀，则称A为前缀码（PrefixedCode）。若符号串bi（i=1,2…,m）中，只出现0和1两个符号，则称A为二元前缀码（BinaryPrefixedCode）。{1,01,001,000}是前缀码{1,11,001,0011}不是前缀码

用2元树产生二元前缀码给定一棵二元树T，假设它有t片树叶。设v是T任意一个分支点，则v至少有一个儿子至多有两个儿子。若v有两个儿子，则在由v引出的两条边上，左边的标上0，右边的标上1；若v只有一个儿子，在v引出的边上可标0也可标1。设vi为T的任意一片树叶，从树根到vi的通路上各边的标号组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码。vi中的符号串的前缀均在vi所在的通路上，因而所得集合为二元(0和1组成)前缀码。若T存在带一个儿子的分支点，则由T产生的前缀码不唯一，但T若为完全2元树，则T产生的前缀码就是唯一的了。例图中所示的2元树产生的前缀码为：{1，00，010，011}。因此用1表示A，用00表示B，用010表示C，用011表示即可满足要求。010011100010011当知道了传输的符号出现的频率时，如何选择前缀码，使传输的二进制位尽可能地少呢？先产生最优二元树T，然后用T产生二元前缀码。最优树定义7.10设有一棵二元树，若对其所有的t片叶赋以权值w1、w2、…、wt，则称之为赋权二元树(PowerBinaryTree)；若权为wi的叶的层数为L(wi)，则称为该赋权二元树的权；而在所有赋权w1、w2、…、wt的二元树中，W(T)最小的二元树称为最优树(OptimalTree)。1952年哈夫曼(Huffman)给出了求最优树的方法。该方法的关键是：从带权为W1+W2、W3、…、Wt(这里假设W1≤W2≤…≤Wt)的最优树T’中得到带权为W1、W2、…、Wt的最优树。算法7.11哈夫曼算法：初始：令S=｛W1,W2,…,Wt｝；从S中取出两个最小的权Wi和Wj，画结点vi，带权Wi，画结点vj，带权Wj。画vi和vj的父亲v，连接vi和v，vj和v，令v带权Wi+Wj；令S=(S-｛Wi,Wj｝)∪｛Wi+Wj｝；判断S是否只含一个元素，若是，则停止，否则转2。解题小贴士——使用哈夫曼算法求最优树每次先在权值序列中选两个最小权的结点构造它们的父亲，父结点的权值为它两个儿子的权值之和，然后在权值序列中添加父结点的权值，删除这两个儿子的权值。例7.16求带权7、8、9、12、16的最优树。158916122131527例7.17用机器分辨一些币值为1角、5角、1元的硬币，假设各种硬币出现的概率分别为0.1、0.4、0.5。问：如何设计一个分辨硬币的算法，使所需的时间最少（假设每做一次判别所用的时间相同，以此为一个时间单位）？10.50.50.40.1(a)是否1元1元是5角1角(b)是否5角否是否所需时间：2×0.1+2×0.4+1×0.5=1.5(时间单位)。例7.18已知字母A、B、C、D、E、F出现的频率如下：A——30％，B——25％，C——20％D——10％，E——10％，F——5％构造一个表示A、B、C、D、E、F前缀码，使得传输的二进制位最少。解（1）求带权30,25,20,10,10,5

的最优二元树T。（2）在T上求一个前缀码。0100110100000010101510102025301525455510010110001CFDBAE1051020253015254555100（3）传输100个这样的字母所用的二进制位为：4×(5+10)+3×10+2×(20+25+30)=240（3）设树叶vi带权为w％×100=w，则vi处的符号串表示出现频率为w％的字母。{01，10，11，001，0001，0000}为一前缀码，其中 0000表示F， 0001表示E， 001表示D， 01表示C， 10表示B， 11表示A。传输100个这样的字母所用的二进制位为：4×(5+10)+3×10+2×(20+25+30)=240。内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.87.3.1欧拉图的引入与定义哥尼斯堡（Konigsberg)七桥问题BCADb6b2b5b7b4b1b3ABCDb5b2b1b3b7b4b6欧拉图定义11.2.1设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(EulerianEntry/Circuit)。具有欧拉回路的图称为欧拉图(EulerianGraph)。规定：平凡图为欧拉图。以上定义既适合无向图，又适合有向图。欧拉通路和欧拉回路的特征欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路；欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。解题小贴士——欧拉图的判断1找到一条经过图中每边一次且仅一次的通路（回路），则该图存在欧拉通路（回路）。有欧拉回路的图为欧拉图。例7.19判断下面的图中，是否是欧拉图？是否存在欧拉通路？欧拉图

不是欧拉图但存在欧拉通路

不存在欧拉通路

v3v1v2v4v3v1v2v4v3v1v2v4(c)(a)(b)例7.19判断下面的图中，是否是欧拉图？是否存在欧拉通路？欧拉图

不是欧拉图但存在欧拉通路

不存在欧拉通路

v3v1v2v4v3v1v2v4v3v1v2v4(f)(d)(e)7.3.2欧拉图的判定定理7.5无向图G=<V,E>具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。证明若G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。设G具有一条欧拉通路L=，由于G中无孤立结点，对欧拉通路L的任意非端点的结点，在L中每出现一次，都关联两条边和，而当重复出现时，它又关联另外的两条边，必要性：由于在通路L中边不可能重复出现，因而每出现一次都将使获得2度。若在L中重复出现p次，则deg()=2p。则L经过G中的每条边，因而L经过G的所有结点，所以G是连通的。若端点≠，设、在通路中作为非端点分别出现p1和p2次，则deg()=2p1+1，deg()=2p2+1因而G有两个度数为奇数的结点。若端点=，设在通路中作为非端点出现p3次，则deg()=1+2p3+1=2(p3+1)因而G无度数为奇数的结点。充分性：构造性证明从两个奇度数结点之一开始(若无奇度数结点，可从任一结点开始)构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终(若无奇度数结点，则以回到原出发点而告终)。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点中的一个开始，我们再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起点。将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到得到一条通过图中所有边的通路，即欧拉通路。由定理7.5的证明知：

若连通的无向图有两个奇度数结点，则它们是G中每条欧拉通路的端点。结论推论7.1无向图G=<V,E>具有欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。定理7.6有向图G具有欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。推论7.2有向图G具有欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。欧拉通路与欧拉回路判别准则对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有4个结点的度数均为奇数；也很容易得到例7.19的结论。解题小贴士——欧拉图的判断2连通图的无向图（1）计算所有结点的度数。（2）存在0个奇度数结点则有欧拉回路，是欧拉图；存在2个奇度数结点则有欧拉通路。连通图的有向图（1）计算所有结点的出度和入度。（2）所有结点的入度等于出度则有欧拉回路，是欧拉图；两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1，则有欧拉通路。v3v1v2v4v3v1v2v4v3v1v2v4(c)(a)(b)v3v1v2v4v3v1v2v4v3v1v2v4(f)(d)(e)桥定义11.2.2设G=<V,E>，e∈E，如果p(G-e)＞p(G)称e为G的桥(Bridge)或割边(Cutedge)。显然，所有的悬挂边都是桥。v1v4v2v3v6v5桥算法7.12求欧拉图G=<V,E>的欧拉回路的Fleury算法：（1）任取v0∈V，令P0=v0，i=0；（2）按下面的方法从E-{e1,e2,…,ei}中选取ei+1：①

ei+1与vi相关联；②

除非无别的边可选取，否则ei+1不应该为G’=G-{e1,e2,…,ei}中的桥；（3）将边ei+1加入通路P0中，令 P0=v0e1v1e2…eiviei+1vi+1，i=i+1；（4）如果i=|E|，结束，否则转（2）。要点：

在可能的情况下，不选桥仅有欧拉通路的图中如何找出其中的欧拉通路从v1出发的一条欧拉回路为：v1e1v2e4v5e7v8e11v6例7.20用Fleury算法求欧拉图的一条欧拉回路。v1v7v5v3v2v8v4e1e2e3e4e5e6e10e7e8e9e11e12v6不选桥e8e2v3e5v6e9v2e12v8e3v4e6v7e10v4e8v1

P12=内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.87.4.1哈密顿的引入与定义1859年，威廉.哈密顿爵士正十二面体每个面都是正五边形，三面交于一角20个顶点、30条边和12个面1234567208910111213141516171819平面展开哈密顿图定义7.13经过图中每个结点一次且仅一次的通路（回路）称为哈密顿通路（回路）（HamiltonianEntry/circuit）。存在哈密顿回路的图称为哈密顿图（HamiltonianGraph）。规定：平凡图为哈密顿图。以上定义既适合无向图，又适合有向图。哈密顿通路和哈密顿回路的特征哈密顿通路是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结点的基本通路哈密顿回路是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路如果我们仅用结点来描述的话哈密顿通路就是图中所有结点的一种全排列哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列从定义可看出，若图中存在哈密顿通路（回路），则该图是连通的。又可知平行边与环存在与否不影响图中是否存在哈密顿通路（回路），约定以后讨论均为连通的简单图。解题小贴士——哈密顿图的判断1找到一条经过图中每个结点一次且仅一次的通路（回路），则该图存在哈密顿通路（回路）。有哈密顿回路的图则为哈密顿图。例7.21判断下面6个图中，是否是哈密顿图？是否存在哈密顿通路？哈密顿图

不存在哈密顿通路

不是哈密顿图，但存在哈密顿通路

哈密顿图

不是哈密顿图，但存在哈密顿通路不存在哈密顿通路

v3v1v2v4(a)v3v1v2v4(d)v3v1v2v4(b)v5v6v7v2v4v1v5(c)v3v3v1v2v4(e)v3v1v2v4(f)7.4.2哈密顿图的判定定理7.7设无向图G=<V,E>是哈密顿图，V1是V的任意非空子集，则p(G-V1)≤|V1|其中p(G-V1)是从G中删除V1后所得到图的连通分支数。证明设C是G中的一条哈密顿回路，V1是V的任意非空子集。下面分两种情况讨论：（1）V1中结点在C中均相邻，显然C-V1仍是连通的，但已非回路，因此p(C-V1)=1≤|V1|。（2）V1中结点在C上存在r(2≤r≤|V1|)个互不相邻，C-V1是将C分为互不相连的r段，即p(C-V1)=r≤|V1|一般情况下，V1中结点在C中即有相邻的，又有不相邻的，因此总有p(C-V1)≤|V1|。因C是G的生成子图，从而C-V1是G-V1的生成子图，故p(G-V1)≤p(C-V1)≤|V1|。推论7.3设无向图G=<V,E>中存在哈密顿通路，则对V的任意非空子集V1，都有p(G-V1)≤|V1|+1定理7.7在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利用定理7.7的逆否命题来判断某些图不是哈密顿图，即：若存在V的某个非空子集V1使得p(G-V1)＞|V1|，则G不是哈密顿图。注意：定理7.7给出的是哈密顿图的必要条件，而不是充分条件。v3v1v2v4v5v6v7v2v4v1v5v3解题小贴士——判断不是哈密顿图在图中能够找到V的某个非空子集V1使得p(G－V1)＞|V1|则G不是哈密顿图；在图中能够找到V的某个非空子集V1使得p(G－V1)＞|V1|＋1则G中不存在哈密顿通路。例7.22证明下图中不存在哈密顿回路。证明

在图中，删除结点子集｛d,e,f｝，得到的图，有4个连通分支，由定理7.7知，该图不是哈密顿图，因而不会存在哈密顿回路。dfeabcgih结论定理7.8设G=<V,E>是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,v∈V，均有

deg(u)+deg(v)≥n-1则G中存在哈密顿通路。推论7.4设G=<V,E>是具有n个结点的简单无向图。如果对任意两个不相邻的结点u,v∈V，均有

deg(u)+deg(v)≥n则G中存在哈密顿回路。推论7.5设G=<V,E>是具有n（n≥3）个结点的简单无向图。如果对任意v∈V，均有

deg(v)≥n/2，则G是哈密顿图。注意定理7.8及其推论给出的是哈密顿图（通路）的充分条件，而不是必要条件。在六边形图中，任两个不相邻的结点的度数之和都是4＜6，但六边形图是哈密顿图。v1v4v6v5v3v2解题小贴士——哈密顿图的判断2任意两个不相邻的结点度数之和≥n－1，则存在哈密顿通路。任意两个不相邻的结点度数之和≥n，则存在哈密顿回路，该图为哈密顿图。例7.23某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？解看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因此每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这5处。例7.24判断是否存在哈密顿回路

方法一：删除结点子集{a,b,c,d,e}，得到的图有7个连通分支，该图不是哈密顿图，故不存在哈密顿回路。e541a2b3cdfghijkmnop54123fghijkmnop例7.24判断是否存在哈密顿回路

方法二：若图中存在哈密顿回路，则该回路组成的图中任何结点的度数均为2。因而结点1、2、3、4、5所关联的边均在回路中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其它边，得到右图。它不是连通图，因而图中不存在哈密顿回路。e541a2b3cdfghijkmnop定理7.9设G=<V,E>是有n(n≥2)个结点的一些简单有向图。如果忽略G中边的方向所得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。在右图中，它所对应的无向图中含完全图K5，由定理7.9知，图中含有哈密顿通路。事实上，通路v3v5v4v2v1为一条哈密顿通路。v2v3v1v4v5内容导航CONTENTS历史人物本章导读及学习要求树根树欧拉图偶图

7.1

7.2

7.3

7.4作业

7.5平面图特殊图的应用哈密顿图

7.7

7.6

7.87.5.1偶图的定义定义7.14若无向图G=<V,E>的结点集V能够划分为两个子集V1,V2，满足V1∩V2=

，且V1∪V2=V，使得G中任意一条边的两个端点，一个属于V1，另一个属于V2，则称G为偶图(BipartiteGraph)或二分图(Bigraph)。V1和V2称为互补结点子集，偶图通常记为G=<V1,E,V2>。定义7.15在偶图G=<V1,E,V2>中，若V1中的每个结点与V2中的每个结点都有且仅有一条边相关联，则称偶图G为完全偶图(CompleteBipartiteGraph)或完全二分图(CompleteBigraph)，记为Ki,j，其中，i=|V1|，j=|V2|。偶图没有环。平凡图和零图可看成特殊的偶图。解题小贴士——偶图的判断找到结点集V的两个互补子集，使得每条边的两个端点都各在一个子集中（或者每个子集中的结点间都无边相连），则该图为偶图。例7.23判断下图中的几个图，那些是偶图？那些是完全偶图？v1v2v3v4v5v6v7(a)v6v1v4v3v5v2(d)(b)v1v2v3v4v5(c)v1v2v3v4v5v6v1v4v2v3(e)偶图偶图偶图偶图不是偶图完全偶图K2,3

完全偶图K3,3

完全偶图K3,3

7.5.2偶图的判定定理7.10无向图G=<V,E>为偶图的充分必要条件是G的所有回路的长度均为偶数。证明

必要性：设图G是偶图G=<V1,E,V2>，令C=v0v1v2…vkv0是G的一条回路，其长度为k+1。不失一般性，假设v0∈V1，由偶图的定义知，v1∈V2，v2∈V1。由此可知，v2i∈V1且v2i+1∈V2。又因为v0∈V1，所以vk∈V2，因而k为奇数，故C的长度为偶数。充分性：设G中每条回路的长度均为偶数，若G是连通图，任选v0∈V，定义V的两个子集如下：V1={vi|d(v0,vi)为偶数}，

V2=V-V1。现证明V1中任两结点间无边存在。假若存在一条边(vi,vj)∈E，其中vi,vj∈V1，则由v0到vi间的短程线(长度为偶数)以及边(vi,vj)，再加上vj到v0间的短程线(长度为偶数)所组成的回路的长度为奇数，与假设矛盾。充分性同理可证V2中任两结点间无边存在。故G中每条边(vi,vj)，必有vi∈V1，vj∈V2或vi∈V2，vj∈V1，因此G是具有互补结点子集V1和V2的偶图。若G中每条回路的长度均为偶数，但G不是连通图，则可对G的每个连通分支重复上述论证，并可得到同样的结论。定理7.10的用途在实际应用中，定理7.10本身使用不多，我们常使用它的逆否命题来判断一个图不是偶图：无向图G不是偶图的充分必要条件是G中存在长度为奇数的回路。例如右图中存在长度为3的回路v1v2v4v1，所以它不是偶图。v1v4v2v3解题小贴士——判断不是偶图找到一条长度为奇数的回路，则该图不是偶图。7.5.3匹配定义7.16在偶图G=<V1,E,V2>中，V1={v1,v2,…,vq}，若存在E的子集E’={(v1,v1’)，(v2,v2’)，…，(vq,vq’)，其中v1’,v2’,…,vq’

是V2中的q个不同的结点}，则称G的子图G’=<V1,E’,V2>为从V1到V2的一个完全匹配(CompleteMatching)，简称匹配。在偶图G=<V1,E,V2>中，若存在V1