二部图及匹配

二部图及匹配 *7.5 7.5.1 在许多实际问题中常用到二部图，本节先介绍二部图的基本概念和主要结论，然后介绍它 的一个重要应用—匹配。 7.5.1 若无向图的顶点集能分成两个子集V和V，满足 GVE,,V12 （1）VVV,VV,,，； 1212 （2）uV,vV,，均有，。 ,,,euvE(,)12 则称为二部图或偶图(Bipartite Graph或Bigraph)，V和V称为互补顶点子集，常记为G12 VV。如果中每个顶点都与中所有顶点邻接，则称为完全二部图或完全偶图GVVE,,,G1212 (Complete Bipartite Graph)，并记为K，其中。 rVsV,,,rs,12 由定义可知，二部图是无自回路的图。 图7-55中，都是二部图，其中是完全二部图(),(),(),(),()abcde(),(),(),()bcdeKKKK,,,。 1,32,32,43,3 图7-55二部图示例 显然，在完全二部图中 Kmrs,中，顶点数，边数。 nrs,，rs, 一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面 的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图7-56中可改画()a 成图()b，图()c可改画成图()d。可以看出，它们仍是二部图。 图7-56二部图示例 7.5.1 无向图为二部图的充分必要条件为中所有回路的长度均为偶数。 GVE,,G 331 先证必要性。 设(,,,,)vvvvVV是具有互补节点子集和的二部图。是中任一长度为的回kGG121k12 路，不妨设vV,vV,vV,(,)vv，则，，所以必为偶数，不然，不存在边。 k22m11211m，k1 再证充分性。 设是连通图，否则对的每个连通分支进行证明。设只含有长度为偶数的GVE,,GG 回路，定义互补节点子集vV,VV和如下：任取一个顶点，令 012 VvvVdvv,,,{()(,)}为偶数10 VVV,, 21 现在证明V中任意两节点间无边存在。 1 假若存在一条边(,)vvE,vvvV,,v，且，则由到间的最短路（长度为偶数）， 边ijij1i0 (,)vvvv和到间的最短路（长度为偶数）所组成的回路的长度为奇数，与假设矛盾。 ijj0 同理可证V中任意两节点间无边存在。 2 故(,)vvvV,vV,V中的每条边必具有形式，其中，， 即是具有互补节点子集GGijj2i11 V和的一个二部图。 2 利用定理7.5.1可以很快地判断出图7-57中的、是二部图，而则不是二部图。 ()a()c()b 图7-57 7.5.1 六名间谍a被擒，已知懂汉语、法语和日语，懂德语、俄语和日abcdef,,,,,b语，ce懂英语和法语，懂西班牙语，懂英语和德语，懂俄语和西班牙语，问至少用几个fd 房间监禁他们，能使在一个房间里的人不能直接对话。 以六人abcdef,,,,,为顶点，在懂共同语言的人的顶点间连边得图（如图7-58()a所G 示），因为中没有奇圈，所以是二部图（如图7-58()b所示），故至少应有两间房间即可。 GG 图7-58 7.5.2 二部图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题” 和“最优分配问题”等运筹学中的问题上有重要的应用。 332 Vxxx,{,,,}nmn首先看实际中常碰见的问题：给个工作人员安排项任务，个人用12n 表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中个任务，那么kk(1),如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？ 例如，现有xxxxx,,,,yyyyy,,,,xyyx五个人，五项工作。已知能胜任和，12345123451122 yyxyyxyyxyyy能胜任和，能胜任和，能胜任和，能胜任、和。如何安排233254135345才能使每个人都有工作做，且每项工作都有人做？ 显然，我们只需构造这样的数学模型：以yxx和（i，j=1，2，3，4，5）为顶点，在与jii其胜任的工作y之间连边，得二部图，如图7-59所示，然后在中找一个边的子集，使得GGj 每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹 配的基本概念和术语。 图7-59匹配问题示意图 7.5.2 设无向图 ，中有边集，且在中任意两条边都没有公共MMEGVE,,G, 的端点，称边集为图的一个匹配(Matching)。中一条边的两个端点，叫做在下是配MMMG 对的。如果M中不存在匹配，使得，则称为最大匹配(Maximum Matching)。 MMM,G11 对于vv的一个匹配，若节点与中的边关联，则称是饱和的(Saturated)，否则MMMG 称v是不饱和的。 M 7.5.3 设二部图,,vVv，是的一个匹配。若，均是饱和的，MMGVVE,,,G112 则称VVV,,vVv是对的完全匹配（简称―完全匹配）；若，均是饱和的，则称是MMM1212 VVVVV对的完全匹配（简称—完全匹配）。若既是―完全匹配，又是―完全匹配（即M21212图的每个顶点都是饱和的），则称是完全匹配(Complete Matching)。 MG 显然，完全匹配是最大匹配，但反之不然。 7.5.2（1）在图7-59中，边集Mxyxyxyxyxy,{(,),(,),(,),(,),(,)}是一个匹1122354354 配，而且是是一个最大和完全匹配。 （2）在图7-60M,{(1,5),(2,7),(3,9),(4,8)}M,{(1,6),(2,7),(3,9)()a中，边集和，12 V(4,8)}()b都是图的最大匹配，也是―完全匹配，但不是完全匹配。在图7-60中，边集G1 M,{(1,4),(2,5),(3,6)}是完全匹配。 333 图7-60 为了寻求二部图的最大匹配，下面交替路和可扩路两个概念。 7.5.4 设是一个二部图，是图的一个匹配，是中的一条路，MLGVVE,,,GG12 如果是由属于和不属于的边交替出现组成，则称为的交替路(Alternating Path)。LMMLMG 如果交替路的始点和终点都是不饱和点，则称为的可扩路(—Extensible Path)。 LMLMMG 例如，在图7-60L:27394L:16273中，对于匹配，路，，M,{(1,6),(2,7),(3,9)}()a21 L:51627394LL,L:5394，都是交替路，其中的始点和终点都是不饱和点，所以这MM4343 两条路是可扩路。 M 可扩路具有如下性质：可扩路的长度必为奇数，且属于的边比不属于的边少1条。 MM 如果在一条可扩路中把属于中的边从匹配中去掉，把不属于中的边添入到匹配中， MM则得到新的匹配MM，的边数比多１。例如，在图7-60中，对于匹配()aM11 L:51627394L，是可扩路，将中属于中的边，，M,{(1,6),(2,7),(3,9)}(1,6)(2,7)MM44 从匹配中去掉， 把不属于中的边添入到匹配中，则得(3,9)(5,1),(6,2),(7,3),(9,4)MMM到新的匹配M,{(5,1),(6,2),(7,3),(9,4)}M，中的边数由中的3条增至4条。如果图中M11 还存在可扩路， 再按上面的步骤做， 所得到的匹配的边数又多１，一直到图中不存在可扩G路为止。用此方法可逐步得到较大的匹配，直至得到最大匹配。这就是下面的定理。 定理7.5.2 在图中，为最大匹配的充分必要条件是不存在可扩路。 MG 先证必要性。 用反证法。假设中存在一条可扩路，则可以得到比的边数多１的匹配，与为MMMG 最大匹配矛盾。所以中不存在可扩路。 MG 再证充分性。 用反证法。假设MMMM,,不是最大匹配，则存在匹配，使得。令（MMM,,1211 MMGMH[],为对称差运算），设由导出的的子图，因为和都是的匹配，所以MHGG212 MM的任意顶点或是只与（或）中的一条边相关联，或是同时与的一条边及的一条边MM11相关联，其度数至多为2，于是M的每个连通分支或者是一个边交错地属于与的长度为MH1偶数的回路，或者是边交错地属于M与的长度为奇数的交错路。 由于，因而MHMM,11 M中必有一个连通分支，它所含的属于的边比属于的边多，不是回路（因为回路的长PMP1 度均为偶数），它的起点和终点都是不饱和的，也一定是中的不饱和点，因此在中MMGG存在关于的可扩路，这与假设矛盾。 M 求一般图的最大匹配过程比较复杂，下面仅讨论如何在二部图中求最大匹配的问题。 设二部图，在中求最大匹配的关键是寻找可扩路。通常是先构造的一GVVE,,,GG12 个匹配V，再看中有没有不饱和点。 如果没有，那么肯定是最大匹配了；如果有， 我MMM1 们就从这些点出发找可扩路，由可扩路做出一个更大的匹配。寻找可扩路的一个有效MMM方法是标记法， 其过程如下： 首先在V中作一个匹配，用（*）标记中所有不饱和点， 然后交替地进行以下步MMG1 骤（１）和（２）。 （１）选一个Vxxx的新标记过的节点，比如， 用（）标记不通过中的边与邻接且M1iii未标记过的VV的所有节点。 对所有新标记过的节点重复这一过程。 21 （２）选一个yyyV的新标记过的节点，比如， 用（）标记通过中的边与邻接且Mjjj2 未标记过的VV的所有节点。对所有新标记过的节点重复这一过程。 12 334 V执行以上步骤， 直至标记到一个中的不饱和点。从该节点倒向追踪到标记有（*）M2 的节点，就得到一条可扩路。于是也就得到一个边数为||＋１的匹配， 再返回（１）。 如MM 果已不可能标记更多的节点，而V的所有标记的节点均为饱和点，则说明中已不存在MMG2 可扩路，这时就是最大匹配。 M 7.5.3 图7-61是一个二部图， 求其最大匹配。 ()a 图7-61 取图7-61图 Mxyxy,{(,),(,)}V()a的一个匹配。用（*）标记中所有不饱和M31521点xxx,,。 124 （1）选VxxxV的新标记过的节点，用（）标记不通过中的边与邻接且未标记过的M11112yxy的节点；类似地，用（）标记。 122 (2) 选VyyyV的新标记过的节点， 用（）标记通过中的边与邻接且未标记过的M21111 xxy的节点；类似地，用（）标记。 532 (3) 选VxxV的新标记过的节点，因为不存在不通过中的边与邻接的的节点，所以M1332不用（xVxyyxy）标记的节点；用（）标记或，假定用（）标记。 3253453y是不饱和点，标记结束。 M3 从yxyxyxyxy倒向追踪到标记有（*）的节点，就得到一条可扩路或，取前M322534253者，由此得匹配Mxyxyxy,{(,),(,),(,)}。 1223153 对匹配MMM再用标记法（见图7-61知， 图中已不存在可扩路，所以就是最大()b111匹配。 定理7.5.3（霍尔定理） 二部图VV有―完全匹配，当且仅当对中任一子GVVE,,,1112 集NA()，和所有与邻接的点构成的点集，恒有 AA NAA(), 先证必要性。假设VV是二部图的一个―完全匹配，则中的每个MGVVE,,,1112 顶点均是VNA()饱和的。对的任一子集，因的每个顶点在下和中不同的顶点配对，MAAM1 所以有。 NAA(), 再证充分性。假设VV是满足对任何的子集，的二部图，但中没有使AGNAA(),G11 MMV中每个顶点饱和的完全匹配，设是的一个最大匹配，由假设，不使中所有顶点饱G111 335 MMvVv和。设是中的不饱和点，并设是与有关于交错路相连通的所有顶点的集合。由B111 于MMv是一最大匹配，由定理7.5.2可知：为中唯一的不饱和点。 B11 令MV=，TBV,，显然，中的顶点都关于饱和，即它与中的顶点Av,{}BAT112 在MM下配对，于是，且，又因中的每个顶点有关于交错路与NAT(),NA()TA,,111v相连通，因此，所以 NAT(), NAAA()1,,, 与假设矛盾。 NAA(), 7.5.4 设有4个人xxxx,,,yyyyy,,,,，现有5项工作需要做，每个人所能胜任123412345 工作的情况如图7-62所示，问能否使每个人都能分配到一项工作？ 图7-62 这个问题即为：二部图{,,}xxxV是否存在―完全匹配。当取=时，AGVVE,,,134112 {,}yyV=，因此，根据霍尔定理，二部图没有―完全匹配，所以要使每NA()NAA(),251个人都能分配到一项工作是不可能的。 7.5 1．求下面两个二部图的最大匹配。 图7-63 0B,,2．假定是二部图，如何安排中顶点的次序可使的邻接矩阵呈 GGG,,C0,,形式，0为零矩阵。 3．某单位有7个工作空缺ppppppp,,,,,,aaa,,,要招聘，有10个应聘者。12345671210他们能胜任的工作岗位集合分别为：{,,}ppp{,,}ppp{,}pp{,}pp{,}pp，，，，，156267341567 {,}pp{,}pp{}p{}p{}p，，，，。如果规定每个应聘者最多只能安排一个工作，试给2313315 出一种分配 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 使落聘者最少？ 336 2n4．设图是二部图，证明。 (,)nmGm,4 7.6 7.6.1 在一些实际问题中，常常需要考虑一些图在平面上的画法，希望图的边与边不相交或尽量 少相交。如印刷电路板上的布线、线路或交通道路的设计、地下管道的铺设等。下面举一个简 单的例子。 7.6.1 一个工厂有 3 个车间和 3 个仓库。 为了工作需要， 车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？ 如图7-64所示，，，是3个车间，，，是3座仓库。经过努力表明，()aABMPCN要想建造不相交的道路是不可能的，但可以使交叉点最少（如图7-64所示）。此类实际问题()b 涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。本节介 绍平面图的一些基本概念和常用结论。 图7-64 7.6.1 设 是一无向图。如果能把的所有节点和边画在平面上，使得任何GVE,,G 两条边除公共端点外没有其他的交点，则称是一个平面图(Planar Graph)，或称该图能嵌入平G 面；否则，称是一个非平面图。 G 直观上说所谓平面图就是可以画在平面上，使边除端点外彼此不相交的图。应当注意，有 些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。 图7-65平面图和非平面图示例 337 例如，图7-65KK是无向完全图，它是平面图。图7-65是无向完全图，它表面()a()b34上看有相交边，但是把它画成图， 则可以看出它是一个平面图。图是平面图。图经()d()c()e改画后得到图，图经改画后得到图，由定义知它们都是平面图。而图、是无()g()h()i()j()f 向完全图KKK，和图7-64中的两个图，无论怎样调整边的位置，都不能使任何两边除公3,355 共端点外没有其他的交点，所以它们不是平面图，它们是两个最基本、最重要的非平面图，在 平面图理论的研究中有非常重要的作用。 设是平面图，的以无交边的方式画在平面上的图称为平面图的平面嵌入GGG(Imbedding)。如图7-65 中的、、分别为图、、的平面嵌入。 ()c()f()h()b()e()g 关于平面图，以下两个结论是显然的。 7.6.1 若是平面图，则的任何子图是平面图。 GG 7.6.2 若是非平面图，则的任何母图是非平面图。 GG 无向完全图Kn(3),Kn(5),和二部图都是非平面图。 3,nn 7.6.2 设是平面图。将嵌入平面后，由的边将所在的平面划分为GVE,,GGG若干个区域，每个区域称为的一个面(Face)。其中面积无限的面称为无限面或外部面(Exterior G Face)，面积有限的面称为有限面或内部面(Interior Face)。包围每个面的所有边组成的回路称为 该面的边界(Bound)，边界长度称为该面的次数(Degree)，面的次数记为。 deg()RR 例如，图7-65共有2两个面，每个面的次数均为3。7-65共有4四个面，每个面的()a()c次数均为3。图7-65 共有3个面，每个面的次数均为4。图7-65 共有6个面，每个面()f()h的次数均为3。图7-66所示平面图deg()3R,deg()3R,R有4个面，，，的边界为G123eeeeeeeeeeeeeedeg()5R,Rdeg()9R,，，的边界为，。 1679865421078910300 图7-66 关于面的次数，我们有下述定理。 7.6.3 在一个有限平面图中，所有面的次数之和等于边数的二倍，即 G r deg()2Rm, i,i,1 其中，rm为的面数，为边数。 G 注意到等式的左端表示的各个面次数的总和，在计数过程中，的每条边或者是GG两个面的公共边界，为每一个面的次数增加1；或者在一个面中作为边界重复计算两次，为该 面的次数增加2。因此在计算面的次数总和时，每条边都恰计算了两次，故等式成立。 由定理7.6.3可以立即得出： 在任何平面图中次数为奇数的面的个数是偶数。 GG的不同平面嵌入的面的次数数列可能是不同的。图7-67中的，是同一个图的平面G12嵌入，但它们的面的次数数列分别是3,3,5,5和3,3,4,6。 338 图7-67 7.6.2 rnm在1750年数学家欧拉发现，任何一个凸多面体的顶点数，棱数和面数之间满足关系 式： nmr,，,2 这就是著名的欧拉公式。 更一般地，对任意平面图，欧拉公式依然成立。这就是下面的定理和 推论。 7.6.4 设rnm为一个连通平面图，它有个节点，条边和个面，则有。 Gnmr,，,2 对m的边数进行归纳证明。 G 当rmnm=0时，由于是连通的，因此只能是平凡图。这时，=1，=0，=1，GGnmr,，,2 成立。 设时，结论成立，下面证明当时，结论也成立。 mkk,,(1)mk,，1 易见，一个具有条边的连通平面图可以由条边的连通平面图添加一条边后构成。因k，1k 为一个含有条边的连通平面图上添加一条边后仍为连通图，则有三种情况： k （1）所增边为悬挂边（见图7-68），此时的面数不变，节点数增1，边数增1，欧拉()aG 公式成立。 （2）所增边为一个环，此时的面数增1（见图7-68），边数增1，但节点数不变，欧()bG 拉公式成立。 （3）在图的任意两个不相邻节点间增加一条边（见图7-68），此时的面数增1，边()cG数增1，但节点数不变，欧拉公式成立。 图7-68 7.6.5 设是连通的(,)nm平面图，且每个面的次数至少为ll(3),，则 G lmn,,(2) l,2 由定理7.6.3知 r 2deg()mRlr,,,r (为的面数) Gi,i,1 再由Euler公式 nmr,，,2得 339 2m rmn,，,,2l故 l。 mn,,(2)l,2 1 平面图的平面嵌入的面数与的嵌入方法无关。 GG 于是的一个平面嵌入的面数，可直接称为平面图的面数。 GG 2 设是有n个节点()，m条边的简单平面图，则。 Gn,3mn,,36 不妨设,,是连通的，否则可在的连通分支间加边而得到连通图，的节点数GGGG 仍为,,n，边数，所以若定理对成立，则对也成立。 mm,GG 由于n是有个节点()的简单连通平面图，所以的每一个面至少有3条边围成。Gn,3G如果r中有个面，则面的总次数 G 23mr, 即有 2m r,3 代入欧拉公式，可得 2m nm,，,23 从而得到 。 mn,,36 推论2也可直接由定理7.6.5推出，只需令即可。 l,3 3 若有Kn个节点()的简单连通平面图不以为子图，则。 n,3Gmn,,243 由于Knn是有个节点(?3)的简单连通平面图，且中不含，所以的每个面至GGG3少由4条边围成，即，代入定理7.6.5，立即得 l,4 。 mn,,24 4 若是一个简单平面图，则至少有一个节点的度数小于等于5。 GG 当的节点数小于等于6时，结论显然成立。当的节点数大于等于7时，设的GGG 最小度节点的度数为，若，即，由握手定理知 ,,,5,,6 2deg()6mvn,, ,vV, 故 mn,3 与推论2矛盾，所以图中至少有一个节点的度数小于等于5。 G 7.6.2 证明KK和都不是平面图。 3,35 （1）Kn的节点数=5，边数，若它是平面图，则由推论2得，m,10mn,,365 即 K，这是一个矛盾不等式，故不是平面图。 10356,，,5 （2）KKn的节点数=6，边数，且其不含子图，由推论3可知，即m,9mn,,243,33 K，这也是一个矛盾不等式，故是非平面图。 9264,，,3,3 上面给出的定理7.6.4和推论2、推论3、推论4都是一个图是平面图的必要条件，它们可用来判断某个图不是平面图。我们希望找出一个图是平面图的充分必要条件。经过几十年的努 力，波兰数学家库拉托夫斯基（Kuratowski）于1930年给出了平面图的一个非常简洁的充分必要条件。下面就来介绍库拉托夫斯基定理。为此先引入同胚的概念。 340 e7.6.3 设为一个无向图，是的一条边，在中删去边，增加新的节点euv,(,)GGG wwww，使均与相邻接，则称在中插入一个2度节点； 设为的一个2度节点，与uv,GG ww相邻接，在中删去节点及与相连接的边，同时增加新边，则称在(,),(,)wuwv(,)uvuv,G w中消去一个2度节点。如图7-69 所示。 G 图7-69 7.6.4 如果两个无向图GG与同构或通过反复插入或消去2度节点后是同构的，则称12 GG与是同胚的(Homeomorphic)。 12 例如，图7-70所示的4个图是同胚的。 图7-70 7.6.6 (库拉托夫斯基定理) 一个无向图是平面图当且仅当它不含有与KK或同胚3,35的子图。 库拉托斯基定理的必要性容易看出，因为KKKK和均不是平面图，因此与或同胚3,33,355的图也不是平面图。一个无向图若是平面图，则它自然不会含有非平面图作为它的子图。 库拉托夫斯基定理的充分性证明较复杂，这里不再引述。有兴趣的读者可参阅邦迪 (J.A.Bondy)和默蒂(U.S.R.Murty)的《图论及其应用》。 7.6.3 证明图7-71中的（彼得森图）是非平面图。 ()a 图7-71 在彼得森图中有同胚于K的子图(见图7-71()b、()c)，由库拉托夫斯基定理知, 彼3,3 341 得森图不是平面图。 7.6.3 平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色， 那么最少需要多少种颜色呢？1852年，英国青年盖思瑞（Guthrie）提出了用四种颜色可以对地 图着色的猜想（以下简称四色猜想）。1879年肯普（Kempe）给出了这个猜想的第一个证明，但 到1890年希伍德（Hewood）发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明 地图着色用四种颜色就够了，但却可以证明用五种颜色就够了，即五色定理成立。此后四色猜 想一直成为图论中的难题。许多人试图证明猜想都没有成功。直到1976年美国数学家阿佩尔（K.Appel）和哈肯(W.Haken)利用计算机分析了近2000种图形和100万种情况，花费了1200个机时，进行了100多亿个逻辑判断，证明了四色猜想。从此四色猜想便被称为四色定理。但 是，不依靠计算机而直接给出四色定理的证明，仍然是数学界的一个令人困惑的问题。 为了叙述图形着色的有关定理，下面先给出对偶图的概念。 7.6.5 给定平面图FGfff(){,,,},GVE,，，,，其面的集合。若有图12n***GVE,，，,满足下列条件： **（1）对于任意一个面vV,fFG,()，其内部有且仅有一个节点； ii *****（2）对于feE,fe中的面和的公共边，有且仅有一条边，使得，且 evv,(,)Gkjikkij*ee与相交； kk *** （3）当且仅当veeeef只是一个面的边界时，存在一个环且与相交； ikkkki *则称图是图的对偶图(Dual Graph)。 GG *例如，在图7-72中，的边和节点分别用实线和“”表示，而它的对偶图的边和结 GG 点分别用虚线和“? ”表示。 图7-72 从对偶图的定义可以看出，若****GVE,，，,GVE,，，,是平面图的对偶图，则也是GG的对偶图。 *7.6.7一个连通平面图的对偶图G也是平面图，而且有 G *mm,， *nr,， *rn,， *** fFGvV,,(),degdegvf,， ，，，，*iiiGiG 342 ****nmr,,其中和分别是和的节点数，边数和面数。 Gnmr,,G ** 由定义7.6.5对偶图的构造过程可知，G*也是连通的平面图，且，和nr,mm, ***显然成立，下证。因为和均是连通的平面图，所以由欧拉degdegvf,rn,GG，，，，*iGiG 公式有 nmr,，,2 *** nmr,，,2 ***由，可得。 nr,mm,rn, *7.6.6 若图的对偶图同构于，则称是自对偶图(Self-dual Graph)。 GGGG 例如，图7-73给出了一个自对偶图。 图7-73 7.6.8 若平面图 nmGVE,，，,是自对偶图，且有个节点，条边，则。 mn,,21，， 由欧拉公式知 nmr,，,2 由于图nr,GVE,，，,是自对偶图，则有，从而有 22nm,, 即 。 mn,,21，， 从对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的节点 的着色问题。因此，四色问题可以归结为证明：对任意平面图一定可以用四种颜色，对其节点 进行着色，使得相邻节点都有不同颜色。 7.6.7 平面图的(Proper Coloring)（简称着色）是指对的每个节点指派一GG种颜色，使得相邻节点都有不同的颜色。若可用nn种颜色对图着色，则称是—可着色的。GG对图着色时，需要的最少颜色数称为的着色数(Chromatic Number)，记为。 ,GGG，， 于是，四色定理可简单地叙述如下： 7.6.9（四色定理）任何简单平面图都是4—可着色的。 证明一个简单平面图是5—可着色的很容易。 7.6.10（五色定理）任何简单平面图GVE,，，,，均有。 ,G,5，， 只需考虑连通简单平面图的情形。对施行归纳证明。 VG 343 当时，显然，。 V,5,G,5，， 假设对所有的平面图，当时有。现在考虑图GVE,，，,，GVE,，，,Vk,,G,5，，111 vV,G的情形。由定理7.6.5的推论4可知，存在，使得。在图中删Vk,，1deg5v,，，01110去vGv,Gv,，得图。由归纳假设知，是5—可着色的，即。因此只需证,Gv,,5，，0101010明在Gv中，节点可用5种颜色中的一种着色并与其邻接点的着色都不相同即可。 10 若vvv，则与邻接节点数不超过4，故可用与的邻接点不同的颜色对着色，deg5v,，，0000 得到一个最多是五色的图G。 1 若vv，但与邻接的节点的着色数不超过4，这时仍然可用与的邻接点不同deg5v,，，000 的颜色对vG着色，得到一个最多是五色的图。 01 若vvvvv,,,v，且与邻接的5个节点依顺时针排列为和，它们分别着不deg5v,，，0123450 同的颜色红、白、黄、黑和蓝。如图7-74所示。 图7-74 考虑由节点集合 GGv,所诱导的的子图。VvvVGvv,,,,着红色或黄色，，,,13101310 若Gvvv,属于的不同连通分支，如图7-75所示。则将所在的连通分支中的红色与黄色对调，13113 这样并不影响Gv,vG的正常着色，然后将涂上红色即可得到的一种五着色。 1001 若vGvG和属于的同一个连通分支，则由节点集所诱导的的子图Vv,,11331130 ,vvvv中含有一个圈，而和不能同时在该圈的内部或外部，即与不是邻，，VvE,C,,242413013 接点，如图7-76所示。于是，考虑由节点所诱导VvvVGvv,,,,着白色或黑色，，,,2410 子图GG，由于圈的存在，至少有两个连通分支，一个在的内部，一个在的外部（否CCC2424 则图GGGvv中将有边相交，与图是平面图的假设矛盾），则和必属于的不同连通分支，241124作与上面类似的调整，又可得到G的一种五着色。故。由归纳原理，定理得证。 ,G,5，，1 344 图7-75 图7-76 7.6 1． 图7-77()a和()b所示的平面图各有几个面？写出它们各面的边界及次数。 图7-77 345 2． 证明图7-78和是非平面图。 ()a()b 图7-78 3．证明：小于30条边的简单平面图中存在度数小于等于4的节点。 4．设 是简单平面图，面数rG,,12,()3,，证明中存在次数小于或等于4的面。 GG 5．设nm是一个连通平面图， 它有个节点，条边，且每个面由条边围成。 试证 kG kn(2), m,k,2 6．证明具有６个节点和12条边的简单平面图，它的每一个面都是由３条边围成的。 7．设简单图n的节点数?11，则与的补图 中至少有一个不是平面图。 GGGG 7.7 树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年 凯莱在计算有机化学中CH的同分异构物数目时也用到了树的理论。而树在计算机科学中222n， 应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。 7.7.1 7.7.1 一个连通无圈无向图称为无向树(Undirected Tree) (简称为树)，记作。树中TT度数为1的节点称为树叶(Leaf)（或叶节点），度数大于１的节点称为分枝点(Branch Point )（或内点(Inner Point)）。 一个无圈图称为森林(Forest)。 显然若图是森林，则的每个连通分支是树。 例如，图7-79()a和()b所示的图是树；GG 所示的图是森林。 ()c 图7-79 树和森林示意图 346 7.7.1 设是一个无向图，则以下关于的命题是等价的。 (,)nmTT (1) 是树； T （2）无圈且； Tmn,,1 (3) 连通且； Tmn,,1 （4）无圈，但增加任一新边，得到且仅得到一个圈。 T （5）连通，但删去任一边便不连通()。 Tn,2 （6）的每一对节点间有唯一的一条通路()。 Tn,2 (1) （2） , 由树的定义可知n无圈。下证。对进行归纳证明。 Tmn,,1 当时，，显然。 n,1m,0mn,,1 假设时结论成立，现证明时结论也成立。 nk,nk,，1 由于树是连通而无圈的，所以至少有一个度数为1的节点vv，在中删去及其关联边，T便得到v个节点的连通无圈图。由归纳假设它有条边。再将顶点及其关联边加回得到原k,1k 图，所以中含有个顶点和条边，故结论成立。 TTk，1mn,,1k 所以树是无圈且的图。 mn,,1 (2) （3） , 用反证法。若TTT不连通，设有个连通分支() ，，，，其节点数分别TTkk,212k是nnn,,,mmm,,,，边数分别为，于是 12k12k kk nnmm,,, ii,,ii,,11 kk mmnnkn,,,,,,,(1)1 ii,,ii,,11 得出矛盾。所以是连通且的图。 Tmn,,1 (3) （4） , 首先证明n无圈。对作归纳证明。 T 当时，，显然无圈。 n,1mn,,,10 假设节点数为nv时无圈，今考察节点数是时的情况。此时至少有一个节点其度数n,1 ,,vvdeg()1v,。我们删去及其关联边得到新图，根据归纳假设无圈，再加回及其关联边TT又得到图，则也无圈。 TT 其次，若在连通图v(,)vvv中增加一条新边，则由于中由到存在一条通路，故必TTjiji有一个圈通过vv(,)vvvv，。若这样的圈有两个，则去掉边，中仍存在通过，的圈，Tjjijii 与(,)vv无圈矛盾。故加上边得到一个且仅一个圈。 Tij (4) （5） , 若vv(,)vvvv不连通，则存在两个节点和，在和之间没有路，若加边不会产生圈，Tjjijii 但这与假设矛盾，故是连通的。又由于无圈，所以删去任一边，图便不连通。 TT (5) （6） , 由连通性知，任意两点间有一条路径，于是有一条通路。若此通路不唯一，则中含有圈，T 删去此回路上任一边，图仍连通，这与假设不符，所以通路是唯一的。 (6) （1） , 显然连通。下证无圈。用反证法。若有圈，则圈上任意两点间有两条通路，此与通TTT 路的唯一性矛盾。故是连通无圈图，即是树。 TT 347 7.7.2 任一棵树中，至少有两片树叶(节点数时)。 Tn,2 设是一棵树（），由定理7.7.1， 有 (,)nmTn,2 n deg()22(1)22vmnn,,,,, （1） i,i,1 若中无树叶，则中每个节点的度数，则 TT,2 n deg()2vn, （2） i,i,1 若中只有一片树叶，则中只有一个节点度数为1，其他节点度数，所以 TT,2 n deg()2(1)22vnn,,,, （3） i,i,1 (2)，(3)都与(1)矛盾。所以中至少有两片树叶。 T 由定理7.7.1 所刻画的树的特征可见：在节点数给定的所有图中，树是边数最少的连通图， 也是边数最多的无圈图。 由此可知，在一个图中， 若， 则是不连通的； (,)nmmn,,1GG若，则必定有圈。 mn,,1G 7.7.1 设是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求的树叶TT数。 设树x有片树叶，则的节点数 TT nx,，，，213 的边数 T mnx,,,，15 又由 n 2deg()mv, i,i,1 得 2(5)223143，,，，，，，，xx 所以，即树有9片树叶。 Tx,9 7.7.2 1 7.7.2 若无向(连通图) 的生成子图是一棵树，则称该树是的生成树或支撑树GG(Spanning Tree)，记为TTT。生成树中的边称为树枝。图中其他边称为的弦。所有这些GGGG弦的集合称为T的补。 G 例如，图7-80中TTT()b、所示的树、是图()a的生成树，而()d所示的树不是图()a()c123的生成树。、()g所示的树是图的生成树。一般的，一个图的生成树不唯一。 ()f()e 348 图7-80 考虑生成树Teeee,,,Teee,,T{,,}eeeT，可知是的树枝，是的弦，集合是的补。11234156715671生成树有其一定的实际意义。 7.7.2 某地要兴建５个工厂，拟修筑道路连接这５处。经勘测其道路可依如图7-80的()a无向边铺设。为使这５处都有道路相通，问至少要铺几条路？ 解：这实际上是求的生成树的边数问题。 G 一般情况下，设连通图nmnn有个节点，条边。由树的性质知，有个节点，－1条TG 树枝，条弦。 mn,，1 在图7-80中，，则，所以至少要修４条路才行。 ()an,5n,,,,1514 由图7-80可见，要在一个连通图中找到一棵生成树，只要不断地从的回路上删去一GG条边，最后所得无回路的子图就是的一棵生成树。于是有以下定理。 G 7.7.3 无向图有生成树的充分必要条件是为连通图。 GG 先采用反证法来证明必要性。 若不连通，则它的任何生成子图也不连通，因此不可能有生成树，与有生成树矛盾，GG故是连通图。 G 再证充分性。 设连通，则必有连通的生成子图，令是的含有边数最少的生成子图，于是中TTGGG 必无回路（否则删去回路上的一条边不影响连通性，与含边数最少矛盾），故是一棵树，即TT生成树。 2 7.7.3 设TT是一连通的带权图，则的生成树为带权生成树，的树枝GVE,,GGG所带权之和称为生成树TCT()T的权(Weight)，记为。中具有最小权的生成树称为的GGGGG最小生成树(Minimal Spanning Tree)。 最小生成树有很广泛地应用。例如要建造一个连接若干城市的通讯网络，已知城市vv和ji 349 之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树T。 G 下面介绍求最小生成树T的克鲁斯克尔（Kruskal)算法。 G 此方法又称为“”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤 如下： 1) 在中选取最小权边，置边数i＝1。 G 2) 当i＝n－1时，结束。否则，转3)。 3) 设已选择边为eee,,,eee,,,e，在中选取不同于的边，使G12i12ii，1{,,,eee,}ee无圈且是满足此条件的最小权边。 12ii，1i，1 4) 置i为i＋1， 转2)。 设TnT为由上述算法构造的一个的子图，它的节点是的个节点，的边是GG00eee,,,TT，且无圈。由定理7.7.1可知是一棵树，且为图的生成树。 G121n,00 下面证明T是最小生成树。 0 设图TTT的最小生成树是。若与相同，则是图的最小生成树。若与不同，TTTGG000 则在eeTeee,,,中至少存在一条边，使得不是的边，但是的边。因为是树，TTT0i，1i，112i 我们在eTeT中加上边，必有一个圈，而是树，所以中必存在某条边不在中。对于TCCi，100 树,,,eeCTCTCeCe()()()(),，,，若以边置换，则得到一棵新树，树的权，因TTTi，1i，1 为,CeCe()()0,,CeCe()(),是最小生成树，故，即或。因为CTCT()(),Ti，1i，1 ,eee,,,,e{,,,eee,}eCeCe()(),是的边，且在中无圈，故不可能成立，否T12ii，112ii，1i，1 则在,Teee,,,eCeCe()(),e中，自之后将取而不能取，与题设矛盾。于是，因此T012ii，1i，1 ,,TT也是的最小生成树，但是与的公共边比与的公共边数多1，用置换，重复上TTTTG00 述过程直到得到与,TTT有条公共边的最小生成树，这时就是，故是最小生成树。 Tn,1000 7.7.3 求图7-81(0)中有权图的最小生成树。 因为图(a)中nn＝8，所以按算法要执行－1＝7次，其过程见图7-81(b)~(h)所示。 7-81 350 7.7.4 图7-82所示的赋权图表示七个城市及架起城市间直接通讯线abcdefg,,,,,,G 路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。 7-82 该问题相当于求图T的最小生成树问题，此图的最小生成树为图7-82中的，因此如GG图T架线使各城市间能够通讯，且总造价最小，最小造价为： G WT()134892348,，，，，，, G 7.7 1．一棵树有5个度为2的节点，3个度为3的节点，4个度为4的节点，2个度为5的T 节点，其余均是度为1的节点，问有几个度为1的节点？ T 2．一棵树有nnn个2度节点，个3度节点，，个度节点，求其叶节点的数目。 k23k 3． 求出K中所有不同构的生成树。 6 4．对于图7-83和，利用克鲁斯克尔算法求一棵最小生成树。 ()a()b 图7-83 5．今有煤气站 ，将给一居民区供应煤气，居民区各用户所在位置如图7-84所示，铺设A 各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的 煤气管道路线，并求所需的总费用。 351 图7-84 n 6．设ndn,,2(1)ddd,,,是个正整数（），若，则存在一棵无向树，其节n,2i,12ni,1 点度数分别为ddd,,,。 12n 7.8 7.8.1 7.8.1 一个有向图，若不考虑边的方向，它是一棵树，则称这个有向图为有向树 (Directed Tree )。 一棵有向树，如果恰有一个节点的入度为０，其余所有节点的入度都为１， 则称为根树(Rooted Tree)，其中入度为０的节点称为树根(Root)，出度为０的节点称为树叶，出度不为０的节点称为分枝点或内点。 例如，图7-85、、和均为有向树，其中只有和为根树。在根树图()a()b()d()d()d()c()c vvvv,,中，为树根，为分枝点，其余节点为树叶。习惯上我们把根树的根画在上方，叶画1123 在下方，这样就可以省去根树的箭头，如图7-85所示。 ()e 在根树中，称从树根到节点vv的距离为该点的层次。这样对图7-85中的根树，的层()d1 次为０，vv,的层次为１，其余节点的层次均为２。 23 图7-85 352 vvv7.8.2 在根树中，若从v到可达，则称v是的祖先，是v的后代；又若〈v，jjjiiiivvvvv〉是根树中的有向边，则称是的父亲，是的儿子；如果两个节点是同一节点的儿jjjii 子，则称这两个节点是兄弟。 7.8.3 在根树中，任一节点v及其v的所有后代和从v出发的所有有向路中的边构成的 子图称为以v为根的子树。根树中的节点u的子树是以u的儿子为根的子树。 在现实的家族关系中，兄弟之间是有大小顺序的，为此我们引入有序树的概念。 7.8.4 如果在根树中规定了每一层次上节点的次序，这样的根树称为有序树(Ordered Tree)。在有序树中规定同一层次节点的次序是从左至右。例如，图7-85和均为有序树。 ()d()c 7.8.5一个有向图，如果它的每个连通分支是有向树，则称该有向图为(有向)森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林是有序森林。例如，图7-86是一个有序森林。 图7-86 m7.8.2 m在树的实际应用中，我们经常研究完全叉树。 7.8.6 在根树mmm中，若节点的最大出度为，则称为叉树(-ary Tree)。如果的TTT每个分枝点的出度都恰好等于mmmm，则称为完全叉树(Complete -ary Tree)。若叉树的所T 有叶节点在同一层，则称它为正则mm叉树(Regular -ary Tree)。二叉树(Binary Tree )的每个节点vvvv至多有两棵子树，分别称为的左子树和右子树。若节点只有一棵子树，则称它为的左子树或右子树均可。若mm是（正则）叉树，并且是有序树，则称为元有序（正则）树。 TT 例如，在图7-87是一棵二叉树，而且是正则二叉树；图7-87是一棵完全二叉树；图()a()b 7-87是一棵三叉树，而且是正则三叉树；图7-87()d是一棵完全三叉树。 ()c 图7-87 有很多实际问题可用二叉树或m叉树表示。 7.8.1 甲、乙两人进行球赛， 规定三局两胜。图7-88表示了比赛可能出现的各种情况（图 中节点标甲者表示甲胜，标乙者表示乙胜），这是一棵完全二叉树。 353 图7-88 m叉树中，应用最广泛的是二叉树。由于二叉树在计算机中最易处理，所以常常需要把一 棵有序树转换为二叉树。其一般步骤为： (1) 从根开始，保留每个父亲与其最左边儿子的连线，删除与别的儿子的连线； (2) 兄弟间用从左向右的有向边连接； (3) 用如下方法选定二叉树的左儿子和右儿子：直接处于给定节点下面的节点作为左儿子； 对于同一水平线上与给定节点右邻的节点作为右儿子，依次类推。 7.8.2 将图7-89所示的三叉树转换为一棵二叉树。 ()a 对图进行步骤(1)、(2)得图，再按步骤(3)得图。 图7-89即为所求的二叉()a()b()c()c 树。 反过来，我们也可将图还原为图。 ()a()c 图7-89 用二叉树表示有序树的方法，可以推广到有序森林上去，只是将森林中每棵树的根看作兄 弟。其步骤为： (1) 先把森林中的每一棵树表示成一棵二叉树； (2) 除第一棵二叉树外，依次将每棵二叉树作为左边二叉树的根的右子树，直到所有的二 叉树都连成一棵二叉树为止。 7.8.3 将图7-90 ()a所示的有序森林转换为一棵二叉树。 如图7-90()b的二叉树即为所求。 354 图7-90 关于完全m叉树，我们有如下定理。 7.8.1 在完全m叉树中，若树叶数为，分枝点数为，则有 it (1)1mit,,, 由假设知，该树有个节点，由定理7.7.1知，该树边数为。因为所有节点it，it，,1 出度之和等于边数，所以根据完全m叉树的定义知， miit,，,1即 。 (1)1mit,,, 7.8.4 假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要求9个数x，1 xx，，之和，问至少要执行几次加法指令？ 29 用节点表示每个数，把9个数看成树叶，将表示3个数之和的节点作为它们的父亲节点。这样本问题可理解为求一个完全三叉树的分枝点的个数问题。 由定理7.8.1知，有 (31)91,,,i由此得 ＝４。 i 所以至少要执行 4 次加法指令。 图7-91表示了两种可能的计算顺序。 图7-91 355 7.8.5 设有33盏灯，拟公用一个电源，则至少需要多少个5插头的接线板 ? 把33盏灯看成树叶，将5插头的接线板看成分枝点，这样本问题可理解为求一个完全 5叉树的分枝点的个数的问题。 i 由定理7.8.1知， 有 (51)331,,,i 由此得 ＝8 i 所以至少需要8个5插头的接线板。 7.8.6 8枚硬币问题。若有8枚硬币，其中 7 枚重量相等，只有1枚abcdefgh,,,,,,, 稍轻。现要求以天平为工具，用最少的比较次数挑出轻币来。 可用图7-92所示的树表示判断过程。从图中可知，只需称2次即可挑出轻币。这种用于描述判断过程的树叫判定树。 图7-92 7.8.3 www,,,7.8.7 设有一棵二叉树，有片树叶。使其树叶分别带权的二叉树称为带t12t权二叉树(Weighted Binary Tree)。 7.8.8 设有一棵带权www,,,Lw()w的二叉树，其权为的树叶的层为。 T12tii （1）该带权二叉树的权WT()定义为 t WTwLw()(),, ii,i,1 （2）在所有带权www,,,的二叉树中，WT()最小的树称为最优二叉树(Optimal Binary 12t Tree)。 1952年哈夫曼（Huffman）给出了求带权www,,,的最优二叉树的方法： 12t 令www,,,www,,,wvS,{}，，是树叶所带的权（it,1,2,,）。 12t12tii （1）在wvvwvS中选取两个最小的权，，使它们对应的顶点，做兄弟，得一分支点，jjijii令其带权为www,，。 ijij （2）从wwwS中去掉，，再加入。 ijii （3）若S中只有一个元素，则停止，否则转到(1)。 7.8.7 求带权7， 8， 9， 12， 16的最优二叉树。 图7-93()a～()d给出了哈夫曼（Huffman）算法的全过程。 356 图7-93 需要注意的是，最优二叉树不是唯一的，下面图7-94中的两个图都是带权1，2，3，4，6 的最优二叉树。 图7-94 7.8.4 1 利用二叉树可以表示算术表达式或某些命题公式，其方法是：将表达式的运算符（在计算 机中分别以“＋”、“－”、“*”、“／”、“?”表示加、减、乘、除、乘方运算）或命题公式中的联结 词作为分枝点，将运算量（常数和变量或命题变元和命题常量等）作为叶节点画出二叉树。如 果是二元运算，则相应地分枝点有左、右两个儿子，如果是一元运算，则相应地分枝点有直接 儿子。 7.8.8 用二叉树表示算术表达式()/()abcde,,， 该算术表达式的二叉树表示如图7-95所示。 357 图7-94 7.8.9 用二叉树表示命题公式。 (())(())PPQPQR,，,,，,,， 该命题公式的二叉树表示如图7-96所示。 图7-96 2 数据结构中，在使用树作数据结构时，经常需要遍访二元有序树的每一个节点，就是检查 存储于树中的每一数据项。对于一棵根树的每一个节点都访问一次且仅访问一次称为遍历或周 游一棵树。二叉树的遍历算法主要有下列3种： （1 前序遍历算法的访问次序为： 1）访问根； 2）在根的左子树上执行前序遍历； 3）在根的右子树上执行前序遍历。 2 中序遍历算法的访问次序为： 1）在根的左子树上执行中序遍历算法； 2）访问根； 3）在根的右子树上执行中序遍历算法。 3 后序遍历算法的访问次序为： 1）在根的左子树上执行后序遍历算法； 358 2）在根的右子树上执行后序遍历算法； 3）访问根。 7.8.10 （1）用二元有序树表示算术表达式。 ()()()abcdefgh，,,，,,,，，，，，， （2）用三种方法遍历此树，写出遍历结果。 （1）该算术表达式的二元有序树表示如图7-97所示。 图7-97 （2）对于图7-97所示的二元有序树，进行前序遍历的结果为： ,,,，，,,()()()abcdefgh，，，，，， 对于图7-97所示的二元有序树，进行中序遍历的结果为： ()()()abcdefgh，,,，,,,，，，，，， 对于图7-97所示的二元有序树，进行后序遍历的结果为： ()()()abcdefgh，,，,,,,，，，，，， 3 最优树的一个直接应用就是前缀码的设计。 在远程通信中，我们常用5位二进制码来表示一个英文字母(因为英文有26个字母，而 5)。发送端只要发送一条0和1组成的字符串，它正好是信息中字母对应的字符序列。262, 在接收端，将这一长串字符分成长度为5的序列就得到了相应的信息。这种传输信息的方法称 为等长码方法。若在传输过程中，所有字母出现的频率大致相等，等长码方法是一种好方法。 但是字母在信息中出现的频率是不一样的，例如字母e和在单词中出现的频率要远远大于字母t z和在单词中出现的频率。因此人们希望能用较短的字符串表示出现较频繁的字母，这样就q 可缩短信息字符串的总长度，提高信息传输的效率。对于发送端来说，发送长度不同的字符串 并无困难，但在接收端，怎样才能准确无误地将收到的一长串字符分割成长度不一的序列，即 接收端如何译码呢？例如若用00表示e，用01表示，用0001表示，那么当接收到字符串yt 0001时，如何判断信息是还是呢？为了解决这个问题，我们常常使用前缀码。 yte 7.8.9 设aanaaaaaaa是长度为的符号串，称其子串，，…，分别为1212n1121n, 该符号串的长度为1，2，…，的前缀(Prefix)。 n,1 设,,A,{,,,},,,为一个符号串集合，若中任意两个不同的符号串和互不为前Aj12ni 缀，则称为一组前缀码(Prefix Code)。 A 例如{0，10，110，1110，1111}是前缀码，而{00，001，011}不是前缀码。 7.8.2 任意一棵二叉树的树叶集合对应一组前缀码。 给定一棵二叉树， 对每个分枝点引出的左侧的边标记０，右侧的边标记１。 这样， 由树根到每一片树叶的通路上，有由各边的标号组成的序列，它是仅含０和１的二进制序列， 359 把该二进制序列作为这片树叶的标记。显然，任一树叶对应的二进制序列都不是其他树叶对应 的二进制序列的前缀。因此，任意一棵二叉树的树叶集合对应一组前缀码。 例如，图7-98所示的二叉树对应的前缀码是{000，001，01，10，11}。 图7-98 7.8.3 任何一组前缀码都对应一棵二叉树。 设给定一组前缀码， 表示前缀码中最长符号串的长度。我们画出一棵高度为的正hh则二叉树，并给每个分枝点引出的左侧的边标记０，右侧的边标记１，把由树根到每一节点的 通路上各边的标号组成的二进制序列作为该节点的标号。这样，每一个节点都对应一个二进制 序列，同时，对于长度不超过的每个二进制序列也必对应一个节点。对应于前缀码中的每一h 序列的节点，给予一个标记，并将标记节点的所有后裔和射出的边全部删去，这样得到一棵二 叉树，再删去其中未加标记的树叶，得到一棵新的二叉树，它的树叶的标号的集合就对应给定 的前缀码。 7.8.11 给出与前缀码｛00， 10， 11， 010， 011｝对应的二叉树。 因为该前缀码中最长序列长为３， 如图7-99所示作一个高度为３的二叉树。对二()a 叉树中对应前缀码中序列的节点用方框标记， 删去标记节点的所有后代和边得到所求的二叉树 如图7-99所示。 ()b 图7-99 设26个英文字母出现的概率分别为ppp,,,，所谓最佳编码，就是要寻求一棵有261226 26片叶子，其权分别为Lpl,ppp,,,的完全二叉树，使得码的长度的数学期望值最小。 ii,1226i1,这里lppp,,,是第i个字母的码的长度。这个问题实际上就是给定权，寻求一棵带权i1226ppp,,,的最优树问题。 1226 7.8.12 假设在通讯中，十进制数字出现的频率分别是 0：20%； 1：15%； 2：10%； 3：10%； 4：10%； 360 5：5%； 6：10%； 7：5%； 8：10%； 9： （1）求传输它们的最佳前缀码。 （2）用最佳前缀码传输10000个按上述频率出现的数字需要多少个二进制码？ （3）它比用等长的二进制码传输10000个数字节省多少个二进制码？ （1）令对应的树叶的权wp,100，则 iii w,20w,15w,10w,10w,10；；；；； 01234 w,5w,10w,5w,10w,5； ；； ；。 56789 构造一棵带权5,5,5,10,10,10,10,10,15,20的最优二叉树（见图7-100），数字与前缀码的对应关系见图7-100右侧。 图7-99 即最佳前缀码为：{10，010，111，110，001，0111，0001，0110，00000，00001}。 （2）（2×20%+3×(10%+15%+10%+10%)+4×(5%+10%+10%)+5×(5%+5%)）×10000=32500 即传输10000个数字需32500个二进制码。 （3）因为用等长码传输10个数字码长为4，即用等长的码传输10000个数字需40000个二进制码，故用最佳前缀码传输10000个数字节省了7500个二进制码。 7.8 n1． 证明在完全二叉树中，边的总数等于，这里是叶子数。 2(1)n, 2．设nnnn是一棵二叉树，表示树叶的数目，表示出度为2的节点数，则= +1。 T0202 3．将图7-86所示的有序森林转换为一棵二叉树。 4．构造一棵带权1,3,3,4,6,9,10的最优二元树，并求其权WT()。 5．对图7-101给出的二元有序树进行三种方式的遍历，并写出遍历结果。 361 图7-101 6．通讯中出现的频率分别为： abcdefgN,,,,,,, ace：25 %；：20 % ：15 %；：15 %；：10 %；：5 % ；：5 %；：5 % fgdNb 通过画出相应的最优二元树，求传输它们的最佳前缀码，并计算传输10000个按上述频率出现 的字母需要多少个二进制码。 7.9 在现实生活和生产实践中，有许多管理、组织与 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 中的优化问题，如在企业管理中，如 何制定管理计划和设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接 好，才能使生产任务完成的既快又好；在现有交通网络中，如何使调运的物资数量多且费用最 小等。这类问题均可借助于图论知识得以解决。本节介绍有关网络图中某两点（一般常指始点 和终点）的最短路径问题。 7.9.1 求解给定网络图中某两点（一般常指始点和终点）的最短路径问题广泛应用于各个领域中。 例如，求交通距离最短，完成各道工序所花时间最少，或费用最省等等，都可用求网络最短路 径算法得到解决，而且解法简单、有效。先看一个例子。 7.9.1 图7-102是一个石油流向的管网示意图，vv代表石油开采地，代表石油汇集站，17 箭线旁的数字表示管线的长度，现在要从vv地调运石油到地，怎样选择管线可使路径最短？ 17 图7-102 石油流向的管网示意图 也可以用点代表城市，以连接两点的连线表示城市间的道路，这样便可用图形描述城市间 的交通网络。如果连线旁标注城市间道路的距离或单位运价，就可进一步研究从一个城市到另 一个城市的最短路或运费最省的运输方案。 在动态 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 中，最短路径问题可由贝尔曼最优化原理及其递推方程求解，在阶段明确情况 下，用逆向逐段优化嵌套推进，这是一种反向搜索法；在阶段不明确情况下，可用函数迭代法 逐步正向搜索，直到指标函数衰减稳定得解。这些算法都是依据同一个原理建立的。即在网络 图中，如果 vvvvvvvv是从 到的最短路径，则也必然是从到的最短路径。 1n,11n,11nn1 用图论来分析网络最短路径也是依据上述同一客观规律建立求解算法，只不过表达的形式 相异。下面介绍求解最短路径问题的一种简便、有效的算法—Dijkstra算法。 7.9.2 Dijkstra 362 1959年狄克斯特拉（EWDijkstra）提出了求网络最短路径的标号法，用给节点记标号 来逐步形成起点到各点的最短路径及其距离值，被公认为是目前较好的一种算法。 Dijkstra算法也称为双标号法。所谓双标号，也就是对图中的点v((),)Pv,赋予两个标号：iii 第一个标号Pv()vvvv,表示从起点到的最短路的长度，第二个标号表示在到的最短路上i1i1iivvv前面一个邻点的下标，即用来表示路径，从而可对终点到始点进行反向追踪，找到到的i1n 最短路。 Dijkstra算法适用于每条边的权数都大于或等于零的情况。 Dijkstra算法的基本步骤如下： 1）给起点vvvPv()0,v标号（0，1），从到的距离 ，为起点。 11111 2）找出已标号的点的集合，没有标号的点的集合，求出边集 IJ 。 AvvvIvJ,,,{(,),}ijij ３）若上述边集，表明从所有已赋予标号的节点出发，不再有这样的边，它的另一A,, 节点尚未标号，则计算结束。对已有标号的节点，可求得从v到这个节点的最短路，对于没有1标号的节点，则不存在从v到这个节点的路。 1 若边集，则转下一步。 A,, 4）对于边集(,)vv中的每一条边，计算 Aij TPv,，(),,(,)vv（其中是边的权） ijiijijij找出边TT,min{}(,)vv使得。 stijst 需要注意的是，若上述Tv值为最小的边有多条，且这些边的另一节点相同，则表明存在ijj多条最短路径，因此v应得到多个双标号。 j 5）给弧v((),)PvsPvT(),(,)vv的终点赋予双标号，其中。返回步骤2）。 tttstst 经过上述一个循环的计算，将求出vvv到一个节点的最短路及其长度，从而使一个节点jj1 n得到双标号。若图中共有个节点，故最多计算循环，即可得到最后结果。 n,1 7.9.2 以图7-101给出的石油流向的管网示意图为例，vv代表石油开采地，代表石油17 汇集站，箭线旁的数字表示管线的长度，现在要从vv地调运石油到地，怎样选择管线可使路17径最短？ （1）给起点vvvPv()v标号（0，1），从到的距离＝0，为起点。 11111 （2）标号的点的集合vJvvvvvv,{,,,,,}＝｛｝，没有标号的点的集合，边集 I1234567 AvvvIvJvvvv,,,,{(,),}{(,),(,)} ijij1213 TPv,，,，,()02020, 12112 TPv,，,，,()01515, 13113 min{,}15TTT,,(,)vvv，给边的终点以双标号（15，1）。 121313133 （3）标号的点的集合Ivv,{,}Jvvvvv,{,,,,}，没有标号的点的集合，边集 1324567 AvvvIvJvvvvvv,,,,{(,),}{(,),(,),(,)} ijij123436 T,25T,21， 3436 min{,,}20TTTT,,(,)vvv，给边的终点以双标号（20，1）。 34361212122 363 Ivvv,{,,}Jvvvv,{,,,}（4）标号的点的集合，没有标号的点的集合，边集 1234567 AvvvIvJvvvvvvvv,,,,{(,),}{(,),(,),(,),(,)}ijij24253436 TPv,，,，,()20828, 24224 TPv,，,，,()202444, 25225 min{,,,}21TTTTT,,(,)vvv，给边的终点以双标号（21，3）。 2425343636366 （5）标号的点的集合Ivvvv,{,,,}Jvvv,{,,}，没有标号的点的集合，边集 1236457 AvvvIvJvvvvvvvv,,,,{(,),}{(,),(,),(,),(,)}ijij24253467 TPv,，,，,()212041, 67667 min{,,,}25TTTTT,,(,)vvv，给边的终点以双标号（25，3）。 2425346734344 （6）标号的点的集合Ivvvvv,{,,,,}Jvv,{,}，没有标号的点的集合，边集 1234657 AvvvIvJvvvvvv,,,,{(,),}{(,),(,),(,)} ijij254567 TPv,，,，,()251035,45445 min{,,}35TTTT,,(,)vvv，给弧的终点以双标号（35，4）。 25456745455 （7）标号的点的集合Ivvvvvv,{,,,,,}Jv,{}，没有标号的点的集合，边集 1234567 AvvvIvJvvvv,,,,{(,),}{(,),(,)} ijij5767 TPv,，,，,()351146,57557 min{,}41TTT,,(,)vvv， 给边的终点以双标号（41，6）。 576767677 至此，全部顶点都已得到标号，计算结束。得到石油开采地vv到汇集点的最短路径， 17即：vvvv,,,v， 由的第一个标号可知路程长41。 13677 7.9.3 Dijkstra (,)vv(,)vv(,)vv无向图中的任一条边均可用方向相反的两条边和来代替。把原来的ijijji无向图变为有向图后，即可用上述的Dijkstra算法求解。 当然，也可以直接在原来的无向图上用Dijkstra算法求解。在无向图上求解与在有向图上 求解的区别在于寻找邻点时不同：在无向图上，只要两节点之间有连线，就是邻点。因此，在 无向图上的求解和在相应的有向图上求解相比，计算过程中的邻点个数可能增多，边集合中的 边数也就随着增多。计算结束时，一定是所有节点都得到了标号，且其最优结果不会劣于相应 有向图的最优结果。 7.9 v1．求图7-103给出的网络图中到其余各点的最短路。 1 364 图7-103 2．求图7-104给出的网络图中v到其余各点的最短路。 1 图7-104 365