《第二章 生成树.docx》由会员分享，可在线阅读，更多相关《第二章 生成树.docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章生成树第二章树教学安排的讲明章节题目：2.1树的特性；2.2割边与割点，2.3生成树学时分配：共2课时本章教学目的与要求：会正确表述关于树的一些基本概念如树、生成树、割边与割点，会用避圈法和破圈法找生成树，会用树的方法描绘一些简单的实际问题课堂教学方案课程名称：2.1树的特性；2.2割边与割点；2.3生成树授课时数：2学时授课类型：理论课教学方法与手段：讲授法教学目的与要求：会正确表述关于树的一些基本概念如树、生成树、割边与割点，会用避圈法和破圈法找生成树，会用树的方法描绘一些简单的实际问题教学重点、难点：1理解树的概念以及树的等价命题；2把握割边与割点的概念；3理解生成树的定义；4把握
2、找生成树的两种方法避圈法和破圈法。教学内容：树是图论中的一个重要概念。树是一种极为简单而又非常重要的特殊图，它在计算机科学以及其它很多领域都有广泛的应用。在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中222nCH的同分异构物数目时也用到了树的理论。各类网络的主干网通常都是树的构造。本节介绍树的基本知识，其中谈到的图都假定是简单图。2.1树的特性定义2.1.1连通无圈的无向图称为无向树，简称为树Undirectedtree。记作T，树中的悬挂点或称T中度数为1的顶点又称为树叶leave或叶顶点，其它顶点称为树枝BranchPoint或内点(InnerPoint)。诸
3、连通分支均为树的图称为森林forest，树是森林。例1图1中a，b为树，c为森林。图1由于树无环也无重边否则它有圈,因而树必定是简单图。树还有等价命题：设T是一个无向(,)nm图，则下面关于T的命题是等价的。(1)T是树；2T无圈且1mn=-；(3)T连通且1mn=-；4T无圈，但增加任一新边，得到且仅得到一个圈。5T连通，但删去任一边便不连通(2n)。6T的每一对顶点间有唯一的一条通路(2n)。证实(1)?2由树的定义可知T无圈。下证1mn=-。对n进行归纳证实。当1n=时，0m=，显然1mn=-。假设nk=时结论成立，现证实1nk=+时结论也成立。由于树是连通而无圈的，所以致少有一个度数为
4、1的顶点v，在T中删去v及其关联边，便得到k个顶点的连通无圈图。由归纳假设它有1k-条边。再将顶点v及其关联边加回得到原图T，所以T中含有1k+个顶点和k条边，故结论1mn=-成立。所以树是无圈且1mn=-的图。(2)?3用反证法。若T不连通，设T有k个连通分支(2k)1T，2T，kT，其顶点数分别是12,knnn，边数分别为12,kmmm，于是11,kkiiiinnmm=11(1)1kkiiiimmnnkn=-=-(3)?4首先证实T无圈。对n作归纳证实。当1n=时，10mn=-=，显然无圈。假设顶点数为1n-时无圈，今考察顶点数是n时的情况。此时至少有一个顶点v其度数deg()1v=。我们
5、删去v及其关联边得到新图T，根据归纳假设T无圈，再加回v及其关联边又得到图T，则T也无圈。其次，若在连通图T中增加一条新边(,)ijvv，则由于T中由iv到jv存在一条通路，故必有一个圈通过iv，jv。若这样的圈有两个，则去掉边(,)ijvv，T中仍存在通过iv，jv的圈，与T无圈矛盾。故加上边(,)ijvv得到一个且仅一个圈。(4)?5若T不连通，则存在两个顶点iv和jv，在iv和jv之间没有路，若加边(,)ijvv不会产生圈，但这与假设矛盾，故T是连通的。又由于T无圈，所以删去任一边，图便不连通。(5)?6由连通性知，任意两点间有一条途径，于是有一条通路。若此通路不唯一，则T中含有圈，删去
6、此圈上任一边，图仍连通，这与假设不符，所以通路是唯一的。(6)?1显然T连通。下证T无圈。用反证法。若T有圈，则圈上任意两点间有两条通路，此与通路的唯一性矛盾。故T是连通无圈图，即T是树。从以上特征性能够看出，树是“最小的连通图，少一边便不连通；树又是“最大的无圈图，多一边便有圈，因此树是以“最经济的方式把其中各顶点连接起来的图。推论2.1.4任何多于一个顶点的树都至少有两片叶。证实设T是一棵(,)nm树2n，则1deg()22(1)22niivmnn=-=-1若T中无树叶，则T中每个顶点的度数2，则1deg()2niivn=2若T中只要一片树叶，则T中只要一个顶点度数为1，其他顶点度数2，所
7、以1deg()2(1)22niivnn=-=-3(2)，(3)都与(1)矛盾。所以T中至少有两片树叶。树的特征可见：在顶点数给定的所有图中，树是边数最少的连通图，也是边数最多的无圈图。由此可知，在一个(,)nm图G中，若1mn-，则G必定有圈。例2设T是一棵树，它有两个2度顶点，一个3度顶点，三个4度顶点，求T的树叶数。解设树T有x片树叶，则T的顶点数213nx=+，T的边数为15mnx=-=+又由12deg()niimv=得2(5)223143xx+=?+?+?+所以9x=，即树T有9片树叶。2.2割边与割点定义2.2.1若无向图,GVE=为连通图，若有点集1VV?，使图G删除了1V的所有顶
8、点后，所得到的子图是非连通图，而删除了1V的任何真子集后所得到的子图还是连通图，则称1V是G的一个割集VertexCutset。若某一个顶点构成一个割集，则称该顶点为割点CutVertex。如图2，b，d，c，e都是割集，顶点c和顶点e都是割点。固然删除顶点a和c图成为不连通的，但因c是a，c的真子集，所以a，c不是割集。图2定义2.2.2若无向图,GVE=为连通图，若有边集1EE?，使图G删除了1E的所有边后，所得到的子图是非连通图，而删除了1E的任何真子集后所得到的子图还是连通图，则称1E是G的一个边割集(EdgeCutest)。若某一条边构成一个边割集，则称该边为割边(CutEdge)或
9、桥(Bridge)。定理2.2.1一个无向连通图G中的顶点v是割点的充分必要条件是存在顶点u和w，使得连接u和w的每条路都经过v。证实充分性：假如连通图G中存在顶点u和w，使得连接u和w的每条路都经过v，则在子图Gv-中u和w必不可达，故v是割点。必要性：假如v是割点，则Gv-中至少有两个连通分支=定理2.2.3无向连通图G中的边e是割边的充分必要条件是e不包含在图的任何基本圈中。证实(,)exy=是连通图G的割边当且仅当x和y在Ge-的不同连通分支中，而后者等价于在Ge-中不存在x到y的路，进而等价于e不包含在图的任何基本圈中。于是定理得证。2.3树与生成树1无向图中的生成树定义2.3.1若
10、无向(连通图)G的生成子图是一棵树，则称该树是G的生成树或支撑树(SpanningTree)，记为T。生成树T中的边称为树枝。图G中其他边称为T的连枝。所有这些连枝的集合称为T的补。例如，图3中()b、()c所示的树1T、2T是图()a的生成树，而()d所示的树3T不是图()a的生成树。()f、()g所示的树是图()e的生成树。一般的，一个图的生成树不唯一。图3考虑生成树1T，可知1234,eeee是1T的树枝，567,eee是1T的连枝，集合567,eee是1T的补。生成树有其一定的实际意义。例3某地要兴建个工厂，拟修筑道路连接这处。经勘测其道路可依如图3()a的无向边铺设。为使这处都有道路
11、相通，问至少要铺几条路？解：这实际上是求G的生成树的边数问题。一般情况下，设连通图G有n个顶点，m条边。由树的性质知，T有n个顶点，n1条树枝，1mn-+条连枝。在图3()a中，5n=，则1514n-=-=，所以致少要修条路才行。由图3可见，要在一个连通图G中找到一棵生成树，只要不断地从G的圈上删去一条边，最后所得无圈的子图就是G的一棵生成树。于是有下面定理。定理2.3.1任一连通图G都至少有一棵生成树。证若G无圈，则G本身为一树。若G有圈。则删去圈上任一边e，Ge仍连通。对Ge重复上述讨论，直到得到G的无圈的连通子图生成树。定理2.3.2无向图G有生成树的充分必要条件是G为连通图。证实先采用
12、反证法来证实必要性。若G不连通，则它的任何生成子图也不连通，因而不可能有生成树，与G有生成树矛盾，故G是连通图。再证充分性。设G连通，则G必有连通的生成子图，令T是G的含有边数最少的生成子图，于是T中必无圈否则删去圈上的一条边不影响连通性，与T含边数最少矛盾，故T是一棵树，即生成树。生成树的求法求一个连通图的生成树有一个简单算法，这个算法就是在一个连通图中破掉所有的圈，剩下不含圈的连通图就是原图一个生成树，这个算法叫做“破圈法可以以用下面的算法来构造连通图的生成树在图G中任意取一条边1e，找一条不与1e构成圈的边2e，然后再找一条不与1e，2e构成圈的边3e，这样继续下去，直到这种经过不能进行
13、，这时所得到的图G就是一个生成树这种算法我们称之为“避圈法2无向赋权图中的最小生成树在实际工作中，有很多问题的可行解方案都能够通过一个赋权有向图表示，例如：物流渠道的设计、物资运输道路的安排、装卸设备的更新、排水管道的铺设等、所以赋权图被广泛应用于解决工程技术及科学管理等领域的最优化问题。通常我们称赋权图为网络，赋权有向图为有向网络，赋权无向图为无向网络。在有向图的讨论中，类似无向图，能够对多重边、环、简单图、链等概念进行定义，只是在无向图中，链与路、闭链与圈概念是一致的，而在有向图中，这两个概念不能混为一谈。概括地讲，一条路必定是一条链。然而在有向图中，一条链未必是一条路，只要在每相邻的两弧
14、的公共顶点是其中一条弧的终点，同时又是另一条弧的始点时，这条链才能叫做一条路这里仅讨论无向赋权图。权p个顶点的连通图T，每边指定一正数，称为权；图的权，是指图中所有边的权之和。T的生成树T的每边权之和是生成树T的权.权能够表示距离、费用和时间等最小生成树设,GVE是一连通的带权图，则G的生成树GT为带权生成树，GT的树枝所带权之和称为生成树GT的权(Weight)，记为()GwT。G中具有最小权的生成树GT称为G的最小生成树(MinimalSpanningTree)。最小生成树有很广泛地应用。例如要建造一个连接若干城市的通讯网络，已知城市iv和jv之间通讯线路的造价，设计一个总造价为最小的通讯
15、网络，就是求最小生成树GT。求最小树通常用下面两种方法。最小生成树普里姆算法1912年提出：普里姆Prim算法构造最小生成树的经过为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。普里姆算法的时间复杂度为On2，与网中的边数无关，适用于求边稠密的网的最小生成树。破圈法：在给定连通图G中，任取一圈，去掉一条最大权边假如有两条或两条以上的边都是权最大的边，则任意去掉其中一条边，在余图中是图G的支撑子图任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图G的最小树。三、最小生成树及其算法如
16、上所述，一个连通的赋权图G，可能有很多生成树设T为图G的一个生成树，若把T中各边的权数相加所得的和数称之为生成树T的权数G的所有生成树中，权数最小者称为G的最小生成树求最小生成树问题有很广泛的实际应用例如把n个城市用高压电缆连接起来建立一个电网怎样能设计一个把n个城市联络起来的电网，使所用的电缆长度之和最短，即费用最小因费用与长度正比，就是一个求最小生成树的问题由树的性质及生成树的定义知，树T为图G的最小生成树的充分必要条件是对T以外的任意边vvij,)，),(,),(),max),(211jiiiiijivvvvvvvvk?其中),(21jiiiivvvvvk?为生成树TV，E的连接vvij
17、和的路，故G最小生成树T必然由那些权数较小而不构成任何回路的边组成下面所介绍的算法都是根据这个基本原理得到的1.克罗斯克尔算法克罗斯克尔算法是1956年提出的，俗称“避圈法步骤如下：1先把G中所有边按权数大小由小到大重新排列，并取权数最小的一条边作为T的一条边2从剩下的边中按1的排列顺序取下一条边，若该边与前已取进T中的边没有构成圈，则把该边取入中作为的一条边，否则舍去，继续按的排列顺序再取下一条边，如此下去直至有n-1条边组成G的最小生成树证实设0T为由上述算法构造的一个G的子图，它的顶点是G的n个顶点，0T的边是121,neee-，且0T无圈。由定理7.7.1可知0T是一棵树，且为图G的生
18、成树。下面证实0T是最小生成树。设图G的最小生成树是T。若T与0T一样，则0T是图G的最小生成树。若T与0T不同，则在0T中至少存在一条边1ie+，使得1ie+不是T的边，但12,ieee是T的边。由于T是树，我们在T中加上边1ie+，必有一个圈C，而0T是树，所以C中必存在某条边e不在0T中。对于树T，若以边1ie+置换e，则得到一棵新树T，树T的权1()()()()iCTCTCeCe+=+-，由于T是最小生成树，故()()CTCT，即1()()0iCeCe+-或1()()iCeCe+。由于12,ieee1,ie+是T的边，且在12,ieee1,ie+中无圈，故1()()iCeCe+不可能成立，否则在0T中，自12,ieee之后将取e而不能取1ie+，与题设矛盾。于是1()()iCeCe+=，因而T也是G的最小生成树，但是T与0T的公共边比T与0T的公共边数多1，用T置换T，重复上述经过直到得到与0T有1n-条公共边的最小生成树，这时T就是0T，故0T是最小生成树。以图11-14为例节点数n=8先按各边权数的权数由小到大排列),(),(),(213322101vvevvevve),(),(),(),(),(),(),(5010749548317436655204vvevvevvevvevvevvevve