第十一章图与树.ppt

《第十一章图与树.ppt》由会员分享，可在线阅读，更多相关《第十一章图与树.ppt（141页珍藏版）》请在三一办公上搜索。

1、第十一章 图与树,先来研究我们班同学名字中有相同汉字的问题。如果我们把每个同学用平面上的点来表示，谁与谁有相同汉字则在其对应的节点之间连一条边，于是这样就构成一个图。,我们再来看看代表图论的起源的哥尼斯堡七桥问题。哥尼斯堡（后来的加里宁格勒）位于立陶宛的普雷格尔河畔。河中有两个小岛，为方便交通，在河两岸及两个小岛之间建有七座小桥（如图11.l（a）所示）。城中居民经常来此游逛，随即提出了这样一个有趣的问题：游人是否可能从两岸或小岛的一处出发，经由每座桥一次且仅一次，然后回到原地。许多人久而不得其解，直到1736年瑞士数学家欧拉（Euler）解决了这一问题。但欧拉只用一个十分简明而又很有代表性的

2、方法-抽象为一张图（如图11.1（b）所示），并进而研究一般的图何时有这样的解。图11.1（b）中的小圆圈叫做结点，用以表示河两岸及两个小岛；结点间的线段或弧线叫做边，用以表示小桥，如果游人可以作出所要求的那种游历，那么必可从图的某一结点出发，经过每条边一次且仅经过一次后又回到原节点。这时，对每个结点而言，每进入一次，总相应地要离开一次，而每次离开不得重复同一条边，因而它应当与偶数条边相联结。由于图11.1之（b）中并非每个结点都与偶数条边相联结，因此欧拉作出结论：游人不可能作出所要求的游历。,像如上这样由结点和联结结点的边所组成的离散结构就是本章所要讨论的图。这种图与我们以前学过的平面几何图

3、形和立体几何图形不同，即它表示的往往是一个事物集中事物之间的关系，上例的图就分别描述的是我们班同学名字集合上的有相同汉字的关系，以及地点集合上有桥的关系。,因此，图可用来解决许多领域的问题。如生态环境里不同物种的竞争、在人事组织里谁影响谁、比赛结果等都可以用图来表示。而网络中两台计算机是否有通信链路连接、区别分子式相同但结构不同的两种化合物、动物群中存在的食物链、如何根据需要安排考试、分配电视台频道、如何最经济地将一些城市连接起来、能否走遍城市里的所有街道而不重复、能否在平面电路板上实现电路等等都可以用图论解决。因此，我们现在所要研究的图是建立和处理离散对象及其关系即离散结构模型的一个重要工具

4、。在各类关系表示、运筹规划作业、网络结构研究、以及计算机程序流程分析中，都会遇到由这种“结点”和“边”组成的图。它在计算机科学及其应用的许多领域，如数据结构、操作系统、编译、人工智能、形式语言、网络理论、信息的组织与检索等，均起着重要作用。它广泛应用于生物学、心理学、遗传学、地理学、物理学、化学、经济学、社会学、语言学、控制论、运筹学等几乎所有的学科，我们可以说几乎每一门学科都可以用图模型来解决，而本章所要讲的树又是一个结构非常优秀的特殊图，它也有极广泛的应用。,111图的基本概念,由上述介绍我们可以简略地说，有点有边即构成图。即给定一个结点集合和这些节点之间联边的情况，这样组成的离散结构就构

5、成一个图。,1112 图的概念,定义11.1 图（graph）G是一个有序二元组，其中：（1）非空集合V(G)称为图G的结点集，其成员称为结点或顶点（nodes or vertices）。结点用拉丁字母或希腊字母来表示。（2）集合 E(G)称为图G的边集,其成员称为边(edges)。边用结点的序偶来表示。结点有序偶表示的边称为有向边（directed edges），节点无序偶表示的边称为无向边（indirected edges）。,当图的边均为有向边时,称该图为有向图（directed graph）；当图的边均为无向边时，称该图为无向图（indirected graph）。以下图论术语是经常会

6、用到的。边e=时，称边e关联端点u，v,并称u为e 的起点,v为e 的终点。边e=（u,v）时，称边e关联结点u，v,并称u，v为e 的端点，这时u，v为邻接点。当边e与e1有共同端点时，称边e，e1为邻接边。当u=v时，和u,v均称为自环。不是任何边的端点（或称不关联任何边，或称不与任何点邻接）的节点称为孤立节点，仅由孤立节点构成的图（E=）称为零图。,图11.1（b）是一个图的直观表示，称为图的图形，可表示为,例11.1（1）某些城市的铁路连接问题用无向图表示：将城市用结点表示，两城市有铁路直通时连一条边。结点集V=北京，天津，济南，南京，苏州，上海，杭州，武汉，广州，边集E=（北京，天津

7、），（天津，济南），（济南，南京），（南京，苏州），（苏州，上海），（上海，杭州），（武汉，广州），（天津，武汉）,图形为：图11.2,（2）有四个程序p1,p2,p3,p4，它们之间的调用关系为：p1调用p2,p2调用p3和p4，可用有向图表示为：程序为结点，一个程序能调用另一个程序则连成一条边，即图为：，图11.3（a）,(b)都是此图的图形：,（3）图11.3为一有向图的图示，可表示为，,我们看到，与几何图形不同，图与图形的结点位置、边的长短、形状无关紧要，图只与结点与边的联结有关系。因此，一个图所画出的图形可以是不惟一的。如果我们把本章最初提到的同学名字之间有一相同汉字则连一条边，当有

8、两个汉字相同时则要连两条边，这我们所谓叫平行边。关于图还有一些很好理解的术语。,定义11.2 设图G为。（1）当V和E为有限集时，称G为有限图，否则称G为无限图。本书只讨论有限图。（2）关联同一对结点的边称为重边,或平行边。含有重边的图为重图。（3）无环和重边的图称为简单图。当G为有限简单图时，也常用（n，m）表示图G有n 个节点，m 条边。（4）任何两个不同结点间都有边关联的简单图，称为完全图。n个顶点的完全图常记作Kn。（5）有时我们还需要在图中的边上或结点上标上一个数字,即所谓权，此时称G为赋权图，如例11.1的（1）边上的权表示两地的距离。,例11.2 图11.1（b）为重图，b1，b

9、2为重边。图11.3为有向图，e1为环，v6为孤立结点。图11.4（a）为简单图，（b）为完全图K5，（c）为赋权图。,11.1.2 结点的度,结点所邻接的边的数目，我们称之为结点的度，它是图的性质的重要判据。,定义11.3 在图中，结点v的度（degree）d(v)是v所关联的边数。在有向图中，结点v的出度（out-degree）是v作为有向边起点的数目，v的入度（in-degree）是v作为有向边终点的数目。因此，结点v的度d(v)是d+(v)与d-(v)的和。当结点v有自环时，自环使其度增加2，其中一个出度，一个入度。,例11.3 图11.5（a）中，d(v1)=5，（b）中d+(v1)

10、=2，d-(v1)=3，d(v1)=d+(v1)+d-(v1)=5。,关于结点的度有下列重要而基础的性质。定理11.1 对任意图G，设其边数为m,顶点集为v1，v2，vn，那么(11-1)证 当一边关联于两个不同结点时，它分别使两结点各增加一度;当一边为一自环时,它给该结点增加两度,因此有一边使各结点的度的总和增加2，因而各结点的度的总和是边的数目的两倍。,当G为有向图时，式（11-1）可改写为(11-2)证明是较容易的，试着自己完成。,定理11.2 图的奇数度顶点必为偶数个。证 反设某图有奇数个奇数度的顶点，那么它们的度的总和是奇数。由于其余顶点为偶数度的，从而这部分结点度的总和为偶数。于是

11、，图的所有顶点的度数总和为奇数（奇数与偶数的和），与定理11.1矛盾。定理得证。,还有两个与度有关的术语。定义11.4 一度的顶点称为悬挂点（pendant nodes）。定义11.5 各顶点的度均相同的图称为正则图（regular graph）。各顶点度均为k的正则图称为k-正则图。当然，完全图都是正则图，而且利用定理11.2很易证明三次正则图有奇数个结点。,11.1.3 子图、补图及图同构,定义11.6 设图G1，G2，如果V1V2，E1E2，称G1为G2的子图（subgraph）。如果G1是G2的子图，且V1=V2，称G1为G2的生成子图（spanning subgraph），。定义11

12、.7 设无向图G1，G2，称G1与G2互为补图，如果V1=V2，E1E2=，且是完全图。,例11.4 图11.5中（a）和（b）都是（c）的子图。（a）和（b）关于（c）互为补图，（c）为完全图K5。两个图可能本质结构是一样的，我们称为同构。,定义11.8 设G1，G2为两个简单图，称G1与G2同构（isomorphic），如果存在一种方式将V1中节点的名一 一对应地置换为V2中节点的名，可使置换得到的图G1 满足G1G2（即 V1V2，E1E2）。,例11.5（1）图 11.6中（a），（c）表示的两图G1，G2是同构的，因为可以如下将V1中节点的名一一对应地置换为V2中节点的名，可使得到的

13、图G1 满足G1G2。其对应置换为：,（2）图11.7中（a），（b）表示的两图G1，G2不是同构的，定义11.9中所说“一一对应的置换”无法找到，因为这种一一对应的置换必定满足a 置换为（它们是两图中仅有的三度顶点），从而使b，c，d分别对应于,，（或它们的另一排列），因而总有G1中一个悬挂点对应于G2中的一个二度结点，因而不可能使得G1G2。,112 路径、回路及连通性,路与回路是图的基本概念，连通性是图的基本特性。许多问题可以用图的通路来解决，如计算机之间能否传递消息的问题、网络上传递邮递、收集垃圾以及故障诊断等的路线有效计划问题。,1121 路径与回路,所谓路就是从一点沿着图中的边到另

14、外一点，回路即为起点和终点重合。,定义11.9 图G的顶点v1到顶点vl的拟路径（pseudo path）是指如下顶点与边的序列：v1,e1,v2,e2,v3,v l-1,el-1,vl（11-3）其中v1,v2,v3,v l-1,vl为G的顶点e1,e2,el-1 为G的边，且ei(i=1,2,l-1)以vi及vi+1为端点，（对有向图G，ei以vi为起点，以vi+1为终点），路径所含的边数l1称为该拟路径的长度。当ei(i=1,2,l-1)各不相同时，该拟路径称为路径（walk），又当vi(i=1,2,l)各不相同时(除v1与vl)，则称此路径为通路（Path）。v1vl的路径称为闭路径（

15、closed walk）；v1=vl的通路称为回路（circuit）。当讨论限于无平行边的图时，上述拟路径、路径、通路等可用顶点序列来表示，例如用（v1,v2,v3,v l-1,vl）代替式（11-3）。,例11.6（1）在图11.9（a）的有向图中：（v1,v2,v3,v1,v2,v5）为一拟路径，长度为5。（v2,v3,v1,v2,v5,v4）为一路径，长度为5。（v2,v3,v4）为一通路，长度为2。（v2,v3,v1,v2,v5,v4,v2）为一闭路径，长度为6。（v2,v3,v1,v2）为一回路，长度为3。（2）在11.9（b）的无向图中：（v2,v3,v4,v5）为一路径（它在（a

16、）中不是路径），长度为3。（v1,v2,v5,v4,v3,v1）为一回路，长度为5。,关于路径和回路我们有定理11.3 在有n个顶点的图G中，如果有从顶点u到v（u v）的拟路径，那么从u到v必有路径，并且必有长度不大于n 1 的通路。证 不设一般性，设G为一简单图。若G有从u到v的拟路径（u=v1,v2,v3,v l-1,vl=v），且没有vivj（i,j=l，2，,l），那么它便是一条通路，且l n l；若G的这一拟路径中有，vivj,则它可表示为（u=v1,v2,vi,vi,v l-1,vl=v）那么从中删去从vi+1到第二个vi之间的所有边及顶点，便得到一条从u到v的更短的拟路径（u=

17、v1,v2,vi,v l-1,vl=v）然后重复上述讨论，直至没有顶点重复出现，从而 得到从u到v的路径和长度不超过n 1的通路。,完全类似地可以证明：定理11.4 在具有n个顶点的图G中，如果有从v到v的闭路径，那么必定有一条从v到v的长度不大于n的回路。,例11.7（1）图11.9（a）中有v2到v4的拟路径（v2,v3,v1,v2,v5,v4）因而可求得从v2到v4的长度为2(4)的通路（v2,v5,v4）。（2）图11.9（b）中有经由v2的闭路径（v2,v3,v1,v2,v5,v4,v2）。从而有经由v2的长度为3（5）的回路（v2,v5,v4,v2）。,11.2.2 连通性,定义1

18、1.10 对于图中顶点u，v，若有一条u到v的路径，则称u到v是可达的（accesible），特别对u=v也称为是可达的。定义11.11 如果对无向图G的任何两个顶点u，v，u到v都是可达的，称G是连通的（connected）。对于有向图，如果G的任何两个顶点都是相互可达的，称G是强连通的；如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称G是单向连通的；如果G的有向边被看作无向边时是连通的，称有向图G是弱连通的。,例11.8 图11.10（a）为一连通图，（b）为强连通图，（c）为单向连通图，（d）为弱连通图，（e）为含两个连通部分即两个连通分支的不连通图。,定理11.5 如果图

19、G恰有两个不同的奇数度的顶点u，v，那么u到v必定是可达的。证 如果u到v不可达，那么G不是连通的，u与v必分属于两个连通分支G1，G2，而G1，G2是G的子图，且都恰有一个奇数度顶点。这是不可能的（定理11.2）。因而u到v是可达的。,下面我们介绍如何对图进行删点和删边以及割点和割边的概念。首先在图中删掉某点v时，同时要删掉关联v的所有边；而在图中删掉某边e时，只将边e 删掉，点不作任何改变。因为这样才能保证图完整。定义 8.12 如果从G中删除点v后得到的图不连通，则称v为割点（cut-nodes）。如果从G中删除边ev后得到的图不连通，则称e为割边（cut-edges）。,例11.9 图

20、11.11中，v1，v2，v4都是割点，而（v1，v4），（v1，v2），（v2，v3）都是割边。,113 图的矩阵表示,我们说图实际上是两个集合：点集和边集，而边是由结点之间连接的，所以图实际上是建立在结点集上的二元关系。因此我们还可以用关系矩阵表示图，当论及图的不同关系就得到图的不同矩阵表示。,1131 邻接矩阵,定义11.13 设G=为一有向图。其中V=v1,v2,vn，那么nn矩阵A=aij，称为图G的邻接矩阵（adjacency matrix），记为AG,我们很易得出：（1）邻接矩阵也可用于无向图，并且无向图的邻接矩阵是对称矩阵。（2）有向图邻接矩阵第i行“1”的个数是结点vi的出度

21、，而第i列“1”的个数是结点vi的入度；而无向图邻接矩阵第i行“1”的个数是结点vi的度。,例11.10(1)零图的邻接矩阵为零矩阵。(2)图11.12(a)的邻接矩阵为图11.12(b)。,以下设A为图G的邻接矩阵，A=aij，A为A的转置矩阵，为矩阵乘运算符。我们知道，若AB=C，A=aij，B=bij，C=cij，那么我们还用Al表示l个矩阵A的乘积。（1）令Al=，那么的意义是：G中从顶点vi到vj的长度为l的拟路径恰为 条。,如例11.10之（2），由计算得 其中=4，因此图中v3到v1长度为3的拟路径为四条。而图11.12中v3到v1恰有四条长度为3的拟路径，它们是（v3,v1,v

22、1,v1），（v3,v4,v1,v1），（v3,v2,v4,v1），（v3,v2,v3,v1）。,11.3.2 路径矩阵与可达性矩阵,定义11.14 设G=为一有向图。其中V=v1,v2,vn，那么nn矩阵A=pij，称为图G的路径矩阵（walk matrix），记为BG,由上可知 BAA(2)A(n)令矩阵PIB，其中I为（nn）单位矩阵，为逻辑加，称P为图G的可达性矩阵，记为PG。,114 树,树就象自然界当中的大树，是一种极为简单而又非常重要的特殊图，因为我们将会发现它的结构和性质非常好，因此它在计算机科学的算法设计、数据结构、网络技术、人工智能、软件工程、知识工程以及其他许多领域都有广

23、泛的应用。最典型的就是菜单树、目录树。,11.4.1 树的基本概念,定义11.15 连通无回路的无向图称为无向树，简称为树（tree）。树中的悬挂点又称为树叶（leave），其它结点称为分支点（branched node）。单一孤立结点称为空树（null tree）。诸连通分支均为树的图称为森林（forest），树也是森林。,例11.12 图11.15中（a），（b）为树，而（c）不是树，但（c）为森林。由于树无自环也无重边（否则它有回路）,因此树必定是简单图。树还有一些重要的性质。,定理11.6 设图T为一树，其顶点数、边数分别是n,m,那么 n m=1 或 m=n 1 证 用数学归纳法，略

24、。,定理11.7 任何树都至少有两片叶。证 设T为任一树，其顶点数、边数分别为n,m。又设T中至多只有一个顶点是叶，那么这与定理11.6矛盾。因此T至少有两片叶。,树还有下列5个等价定义形式。定理11.8 命题“（n，m）图T为树”与下列5命题中的每一命题等价：（1）T无回路且m=n 1。（2）T连通且m=n 1。（3）T无回路，但任意添加边时，T中产生唯一的一条回路。（4）T连通，但删去任一边时便不再连通，因此T的每一边均为割边。（5）任意两个不同顶点之间有且仅有一条通路。证：略,由上面的讨论我们知道，树是一种结构“很优秀”，也是“最经济”的特殊图，但我们考察如下图（图11.16）：此图不是

25、树，因为它有回路。,其生成子图(图11.17)构成树，这棵树对图G很重要，我们常称为图G的生成树。,11.4.2 生成树,定义11.16 如果T为G的生成子图且T为树，则称T为无向图G的生成树（spanning tree）。,定理11.9 任一连通图G都至少有一棵生成树。证 若G无回路，则G本身为一树。若G有回路。则删去回路上任一边e，Ge仍连通。对Ge重复上述讨论，直到得到G的无回路的连通子图生成树。由此可知，对于连通图G我们可以通过依次从回路中删边的方法得到其生成树，此方法常称为破圈法。不过，生成树通常是不唯一的。,例11.13 图11.18（b），（c）为图（a）的两棵生成树。,定义11

26、.11 设T为图G的生成树，称T中的边为树枝（branch），称G T 中的边为弦（chord）。很显然，（n,m）图G的任一生成树T恒有n1条边，mn+1条弦。,由上面我们知道，一个连通图的生成树往往是不唯一的。而对于赋权图我们最关心的也是最有用的是所谓的最小生成树，下面我们来介绍它的概念及生成算法。设G=为连通的边赋权图，W规定了各边的权。设T为G的生成树，那么T中各边权之和W（T）=称为生成树T的权，权最小的生成树称为最小生成树。,对赋权图求最小生成树的问题，在实际应用中是非常广泛的。以下是求最小生成树的克鲁斯克尔（Kruskal）算法。算法的基本思想是，依次从边权中选择权最小的边，但不

27、能出现回路，直至产生一个n 1 条边的无回路的图。此法常形象称为避圈法。算法是正确的。因为算法产生的图无回路，且边数m=n 1，据定理11.8，此图为树。由于它含有G的所有n个顶点，因而是G的生成树。,最后我们补充两点：（1）对于有边权相同的赋权图，克鲁斯克尔算法依然成立。在某一回路中，若两个边权相同且最大，这时删去权最大的哪一条都一样。（2）利用求生成树的破圈法也可求最小生成树，但其算法与避圈法相反。即依次从图的回路中删去边权最大的边，直至没有回路结束。若在某一回路中，两个边权相同且最大，这时可删去其中的任意一条。,例11.15图11.19（a）表示五个城市道路交通图，各边上的权表示两城市之

28、间的距离。现要沿公路假设电话线，将这些城市连接起来，问如何架线最经济。,解：要将这些城市连接起来，又使架线最经济，即要求使该图结点连通、无回路且边权之和最小，即求该图的最小生成树。由避圈法，先取边权是1的边，然后取剩下的边权中最小的，即取边权是2的边，当然取哪一个都行，然后再在剩下的边权中最小的，这时还是取边权是2的边，但再次取时就不能取边权是2的边，因为会产生回路，那只好取边权是3的边，但只能选（b,e）边。这时已选够5-1=4条边，即得最小生成树图11.19（b），其树权为W（T）=1+2+2+3=8。由破圈法，依次从回路中删除边权最大的，即依次删除边（c,e）,（c,d）,（a,d）或（

29、b,d）,因此得最小生成树图11.19（b）。,114.3 根树及其应用,定义11.17（1）如果有向图G不考虑边的方向时构成图，则称G为有向树。（2）有向树T若只一个结点的入度为零，其余结点的入度都为1，则T称为根树（rooted tree），（3）入度为零的结点称为T的树根，出度为零的结点称为T的树叶。,定义11.18 在根树中，（1）从v0经过一条边到达的结点称为v0的儿子，v0称为它们的父亲。vi，vj同为一顶点v的儿子时，称它们为兄弟。（2）从v0经过一些边到达的结点，称为v0的子孙，v0是它们的祖先。（3）树根到叶有唯一的通路，这样的通路中最长一条的长度称为树高。为了图示能表明根树

30、的树根和结点间的父子关系、兄弟关系，通常约定根树的图示中：树根总画在树的顶部，同一顶点的儿子画在同一水平线上。根树可用于表示很多种数据或逻辑关系，下面用一个例子说明这一点。,例11.16 甲乙两人进行乒乓球赛，规定一方连胜两局或胜局首先达到3局者为胜方。问甲乙至少、至多要进行多少局比赛。如果用分支结点表示一局比赛，用关联的两边表示胜负状况，标记甲的边表示甲胜，标记乙的边表示乙胜，那么可用一棵根树来描述比赛的各种可能进程，从而确定比赛至少要进行2局，至多要进行5局（见图11.20）,图11.20是一种特殊的根树，其每个父结点都恰有两个子结点，我们称这样的根树为完全2元树，这是一种最为简单而又特别

31、有用的根树。,定义11.19 除了树叶外，每个结点都有两个儿子的根树称为完全2元树（binary tree）。完全2元树有以下性质。定理11.10 完全2元树的顶点个数n必定是奇数。证 完全2元树中除树根的度为2外，其它顶点的度均为3或1，因此完全2元树度数总和为n 1个奇数的和加2。若n为偶数，则n 1为奇数，从而树的度数的总和为奇数，但这是不可能的，因此n必为奇数。,定理11.11 完全二元树中叶的数目,其中n为树的顶点数。证 设完全二元树T有n个顶点，l片叶和m条边，那么除根和叶以外它有n 1 l 个分支结点，各为3度顶点，于是解出l我们更多的时候是会遇到每个父结点不恰有两个子结点，下面

32、我们来讨论。,定义11.20 每个结点都至多有两个儿子的根树称为二元树（quasibinary tree）。类似地，每个结点都至多有p个儿子的根树称为p元树。除了树叶外，每个结点都恰有p个儿子的根树称为完全p元树。定理11.12 设完全p元树有l片树叶i个分支点，则（p-1）i=l-1。证：因为完全p元树除了树叶外，每个结点都恰有p个儿子的根树，即每个分支点都恰好引出p条边，所以其边数m=pi，又树的顶点数n=l+i，n=m-1，故而pi-1=l+i，即（p-1）i=l-1。,例11.17 设有16盏灯，拟公用一个电源插座，问至少需用多少块具有四插孔的接线板。解：将具有四插孔的接线板看作是完全

33、4元树的分支点，树叶看作电灯，则由定理11.12有需用的接线板数为分支点数，即（4-1）i=16-1，故i=5。,定义11.21 在根树中，对各分支结点的诸儿子规定了次序（例如左兄右弟）的n 元树称为n元有序树；若对各分支结点的已排序的诸儿子规定了在图示中的位置（例如左、中、右），那么该n元有序树又称n元位置树。2元位置树各分支结点的左右儿子分别称为左儿子和右儿子。,例11.18 图11.21（a）,（b）,（c）均为3元树。（a）,（b）作为一般3元树是相同的，但作为3元有序树是不同的。（b）,（c）作为一般3元树和3元有序树是相同的，但作为3元位置树是不同的。我们用一个例子来指出一个重要的

34、事实：任何n元有序树都可以用2元有序树来表示，即可对任何一n元有序树作一系列的变换，使之成为一棵2元位置树，从这一2元位置树中可得到原n元有序树的有关性质，甚至恢复出这一n元有序树。这对计算机很重要，因为计算机处理二元树是最方便的。,图11.22(a)为一4元有序树,为了表示为2元位置树,只要将每个分支结点的诸儿子中的大儿子（以左兄右弟为序）保留为其儿子（左儿子）,而放弃其它儿子,令二儿子为大儿子的右儿子,三儿子为二儿子的右儿子,如此等等，如图11.22(b)所示。11.22(c)是按根树的约定画法重画图11.22(b)所得的、表示图11.22(a)的2元位置树。或简单地讲多元树转变成2元树即

35、保留原来的左儿子，将其原来的右兄弟变成其新的右儿子，即将一棵多元树如11.22(a)直接转换成2元树，如11.22(a)直接得到11.22(c)。,在作出的2元位置树中检索原n元有序树或恢复原n元有序树，只要把每一分支结点的左儿子看作它的大儿子，而将其右儿子看作它的弟兄，删去该分支结点到其右儿子的边，添加该分支结点的父结点到该分支结点的右儿子结点的边。用类似的方法可用2元位置树来表示由n元有序树组成的森林（称为有序森林）。其做法是，将森林中的每一棵n元有序树表示为2元位置树，将它们的树根以父子方式连接起来，,左父右子。图11.23（a）为一3棵有序树组成的有序森林，（b），（c）为表示（a）的

36、2元位置树。二元位置树被大量用于数据的表示，例如表示算术表达式及各种字符串。这时，常常需要遍访每一个结点，以下是三种遍访二元树的算法。（1）先根算法（前序遍历法）（1.1）访问二元树树根r。（1.2）如果r有左儿子，那么又以先根算法遍访r的左子树（以r的左儿子为根的子树）。（1.3）如果r有右儿子，那么又以先根算法遍访r的右子树（以r的右儿子为根的子树）。（2）中根算法（中序遍历法）（2.1）如果二元树树根r有左儿子，那么又以中根算法遍访r的左子树。、（2.2）访问二元树树根r。（2.3）如果二元树树根r有右儿子，那么又以中根算法遍访r的右子树。（3）后根算法（后序遍历法）（3.1）如果二元树

37、树根r有左儿子，那么又以后根算法遍访r的左子树。（3.2）如果二元树树根r有右儿子，那么又以后根算法遍访r的右子树。（3.3）访问二元树树根r。,例11.19 算术表达式 可以用图11.24中的2元树来表示。其中 表示数乘运算，表示指数运算，d2=d 2。分别用三种算法遍访这一2元树，可以得到三种符号串：由先根算法得/-a+bcd2a bc(11-3)由中根算法得 ab+c-d2/ab c(11-4)由后根算法得 abc+d2-abc-/(11-5),式（11-3）称为算术表达式的前置表达式（运算符都放置在运算数据之前），或称其为算术表达式的波兰表示。它的运算方式如式（11-6）所示，与原中置

38、表达式的运算过程一致。由于波兰表示完全不依赖括号，所表示的运算又没有二义性，其优越性是显而易见的。,式（11-4）称为算术表达式的中置表达式（二元运算符都放置在运算数据之间）。由于遍访所得的表达式没有括号，而二元运算符又在运算数据之间，它所表示的运算过程的二义性就在所难免了。因此用中根算法遍访表示算术表达式的2元树是不适当的。式（11-5）称为算术表达式的后置表达式（运算符都放置在运算数据之后），或称其为算术表达式的逆波兰表示。它的运算方式如式（11-7）所示，与波兰表示一样，逆波兰表示与原中置表达式的运算意义相一致。逆波兰表示也完全不依赖括号，所表示的运算也没有二义性。,最后我们再看两个应用

39、根树解决实际问题的例子。例11.20 有10个文件，分别用10个不同的正整数（2，4，5，7，8，10，12，13，15，16）作标记（称为它们的键值）。为了检索方便，可以把它们以根树的结构储存起来，使得每一个顶点上储存的文件的键值大于它的左子树上所有文件的键值，而小于它的右子树上所有文件的键值，如图11.25所示。,这时如果要检索一个文件，只要将其键值与树根的键值做比较，当它比树根的键值小时，便对左子树重复上述步骤；当它比树根的键值大时，便对右子树重复上述步骤。例如键值为8的文件，做两次比较便可找到。,例11.21 有8枚硬币，其中恰有1枚是假币，假币比真币重。试用一架天平称出假币，使称量的

40、次数尽可能地少。图11.26描述了称量的策略，只要称两次便可测出假币。图中八个数字表示八个硬币，结点处标记的两个集合，为一次称量中两盘所放的硬币，假币一定在一次称量中2元树还有两个最重要的应用，即最优树和前缀码。对一棵2元树，设有t片树叶，分别带权w1,w2,wt（不妨设w1w2wt）,称该树为带权2元树。,定义11.21（1）从根结点到树叶的路径称为通路。（2）在带权2元树中，若带权为wi的树叶，其通路长度为L(wi),我们称W（T）=L(wi)为该带权2元树的权。在所有带权w1,w2,wt的2元树中，W（T）最小的那棵树称为 最优2元树。,求最优2元树的最有效方法就是哈夫曼算法：（1）以树

41、叶权中最小的两个为兄弟，将其权之和赋给其父结点；（2）去掉上述两个叶结点，将其父结点作为新的叶结点，其权与其余叶结点的组成新的树叶权序列，重复（1）；（3）直到只有一个结点为止。,例11.22 设有一组权1，3，7，8，8，9。求相应的最优2元树。解：首先以1，3为兄弟将其权之和4作为新的叶结点，即新的权序列为：4，7，8，8，9。依次做下去，分别得序列为：11，8，8，9；11，16，9；20，16；36故得相应的最优2元树为：,前缀码是用在远距离通讯的译码中的。我们知道，在远距离通讯中，常常用0，1字符串作为英文字母的传送信息，因为英文字母共26个，故要用一位、两位、三位、四位的所有二进制

42、0，1字符，但由于字母的使用频率不同，人们希望用较短的序列表示频繁使用的字母。另外一个最重要的问题就是如何将接收到的字符串进行译码。定义11.22 给定一个序列的集合，若没有一个序列是另一个序列的前缀，称该序列集合为前缀码。例如000，001，01，10，11是前缀码，而1，0001，000就不是前缀码。,定理11.13 任意一棵2元树的树叶可对应一个前缀码。证：给定一棵2元树，从每一个分支点可引出两条边，对左侧边标以0，对右侧边标以1，则每片树叶将可标定一个0和1的序列，它是由树根到这片树叶的通路上各边标号所组成的序列。显然，没有一片树叶的标定序列是另一片树叶的标定序列的前缀，因此，任何任意

43、一棵2元树的树叶可对应一个前缀码。,定理11.14任意一个前缀码可对应一棵2元树。证：设给定一个前缀码，h表示前缀码中最长序列的长度。我们画出一棵高度为h的正则2元树，并给每一分支点射出的两条边标以0和1，这样，每个结点可以标定一个二进制序列，它是由树根到该结点通路上各边的标号所确定，因此，对于长度不超过h的每一二进制序列必对应一个结点。对应于前缀码中的每一序列的结点，给予一个标记，并将标记结点的所有子孙和射出的边全部删去，这样得到一棵2元树，它的树叶就对应给定的前缀码。这样前缀码与2元树相互对应，且若前缀码对应的是完全2元树，则可以进行译码。,如：如设000对应h,001对应a,01对应p,

44、1对应y,则前缀码000，001，01，1对应的完全2元树为（图11.28）：于是如果接收到编码信息序列00000101011，则编码信息必须译成000，001，01，01，1，于是编码信息意思为happy。,*11.5 欧拉图与哈密顿图,11.5.1 欧拉图及欧拉路径,定义11.23 图G称为欧拉图（Euler graph），如果图G上有一条经过G的所有顶点、所有边的闭路径。图G称为欧拉路径（Euler walk），如果图G上有一条经过G所有顶点、所有边的路径。本章一开头介绍的哥尼斯堡桥问题，现在可以这样来叙述：图8.l（b）是否为一欧拉图？,定理11.15 无向图G为欧拉图当且仅当G连通，

45、并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。证 这里仅对无向图立论，定理的后半部分仿此可证，不赘述设G为一欧拉图，那么G显然是连通的。另一方面，由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。反之，设G连通，且每个顶点的度均为偶数，欲证G为一欧拉图。为此，对G的边数归纳。,当m=1时，G必定为单顶点的环，如图8.18（a）所示，显然这时G为欧拉图。设边数少于m的连通图，在顶点度均为偶数时必为欧拉图，现考虑有m条边的图G。设想从G的任一顶点出发，沿着边构画，使笔不

46、离开图且不在构画过的边上重新构画。由于每个顶点都是偶数度，笔在进入一个顶点后总能离开那个顶点，除非笔回到了起点。在笔回到起点时，它构画出一条闭路径，记为H。从图G中删去H的所有边，所得图记为G，G未必连通，但其各顶点的度数仍均为偶数（为什么？）。考虑G的各连通分支，由于它们都连通，顶点度数均为偶数，而边数均小于m，因此据归纳假设，它们都是欧拉图。此外，由于G连通，它们都与H共有一个或若干个公共顶点（如图8.18（b）所示），因此，它们与H一起构成一个闭路径。这就是说，G是一个欧拉图。,定理11.12 无向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径

47、(非欧拉图)，当且仅当G连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。,例11.11（1）由于图8.1（b）的四个顶点都是奇数度的，因此它既不是欧拉图也不是欧拉路径。这就是说，无论是否要求回到原地，不重复地走遍七桥是不可能的。（2）奇数(大于1)个顶点的完全图，k为偶数时的k-正则图都是欧拉图。（3）一笔画游戏(笔不离开纸,不重复地画遍纸上图形的所有的边),实质上是一个欧拉图、欧拉路径的判定问题。图8.19（a）可以从一点出发一笔画所有边后回到起点；图8.19（b）可以一笔画所有边，但不能使笔回到起点；图8.19（c）则根本不可能一笔画所有边。,11

48、.5.2 哈密顿图及哈密顿通路,我们仅限于无向图讨论哈密顿图及哈密顿通路。定义11.24 图G称为哈密顿图（Hamilton graph），如果G上有一条经过所有顶点的回路（也称这一回路为哈密顿回路）。称无向图有哈密顿通路(非哈密顿图)，如果G上有一条经过所有顶点的通路(非回路)。,例11.12 图8.20（a）为一哈密顿图，图中粗线表示哈密顿回路。它是正十二面体（图8.20（b）的“平面投影”。哈密顿（爱尔兰数学家）1859年提出一个名叫“周游世界”的游戏，问题正是：能否遍历正12面体的每个顶点一次且仅一次后回到原地。,注意，哈密顿图、哈密顿通路与欧拉图、欧拉路径之间的区别。它们之间几乎没有

49、什么联系。有的图既是哈密顿图又是欧拉图，有的图只是哈密顿图不是欧拉图，有的图只是欧拉图不是哈密顿图，有的图则两者皆非。特别要留意的是,哈密顿图并不要求其哈密顿回路遍历图的所有的边,仅仅要求遍历图的所有的顶点。至今没有一个像欧拉图的充要条件那样的“非平凡的”（不是定义的同义反复）关于哈密顿图、哈密顿通路的充分必要条件，但关于它们的充分性和必要性分别有一些研究成果。,定理11.13 设图G为具有n个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n 1，那么G中有一条哈密顿通路；如果G的每一对顶点的度数之和不小于n，且n3，那么G为一哈密顿图。,证 先证G为一连通图。若不然，G由若干连通分支

50、所组成。令v1，v2分属于连通分支G1，G2；G1，G2各有n1，n2个顶点。显然n1n，n2n，于是deg(v1)n1 1，deg(v2)n2 1，而deg(v1)+deg(v2)n1+n2 2 n 1，与题设矛盾。为证G有哈密顿通路，只要在G中构作出一条长为n1的通路。为此令P为G中任意一条长为p1,pn,的通路，设其顶点序列为v1，v2，vp。我们来扩充这一通路。（1）如果有v v1，v2，vp，它与v1或vp间有边相关联，那么可立即扩充P为长度为p的通路。（2）如果v1，vp均只与原通路P上的顶点相邻，如下可证：G中有一条包含v1，v2，vp，长度为p的回路。,如果v1与vp相邻，那么