《离散数学(7.7树与生成树)ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学(7.7树与生成树)ppt课件.ppt（24页珍藏版）》请在三一办公上搜索。
1、7.5 树与生成树(Trees and Spanning Trees),7.5.1 无向树(Undirected Trees)7.5.2无向图中的生成树与最小生成树(Spanning Trees and Minimal Spanning Trees),7.5.1 无向树(Undirected Trees),树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中2H2n+2的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。,定义7.5.1 一个连通无圈无向图称为无向树(简称为树)
2、。记作T。树中度数为1的结点称为树叶（或终端结点），度数大于的结点称为分枝点（或内点，或非终端结点）。一个无圈图称为森林。显然若图G是森林，则G的每个连通分支是树。如图7.5.1(a)所示的是一棵树；(b)所示的是森林。,图 7.5.1 树和森林示意图,【例7.5.1】判断图 7.5.2中各图是否为树.,图 7.5.2,证：因为 T是一棵n的（n，m）树，所以由定理7.5.1，有,若T中的无树叶，则T中每个顶点的度数2,则 deg(vi)2n,（2）若T中只有一片树叶，则T中只有一个结点度数为1,其它结点度数2,所以,(1),(3),(2),(3)都与(1)矛盾。所以T中至少有两片树叶。证毕。
3、,定理7.5.1 任一树T中,至少有两片树叶(n2时)。,定理7.5.2一个无向图（n,m）图T是树,当且仅当下列5条之一成立。(或者说,这5条的任一条都可作为树的定义。)(1)无圈且m=n-1。(2)连通且m=n-1。(3)无圈,但增加任一新边,得到且仅得到一个圈。(4)连通但删去任一边,图便不连通(n2)。(5)每一对结点间有唯一的一条通路。(n2)。,证:(1)证明由树的定义可知T无圈。下证m=n-1。对n作归纳。n=1时,m=0,显然m=n-1。假设n=k时命题成立,现证明n=k+1时也成立。由于树是连通而无圈,所以至少有一个度数为1的结点v,在T中删去v及其关联边,便得到k个结点的连
4、通无圈图。由归纳假设它有k-1条边。再将顶点v及其关联边加回得到原图T,所以T中含有k+1个顶点和k条边,符合公式m=n-1。所以树是无圈且m=n-1的图。,(2)证明由第(1)条可推出第(2)条。用反证法。若图不连通,设T有k个连通分支(k2)T1,T2,Tk,其结点数分别是n1,n2,nk,边数分别为m1,m2,mk,于是,得出矛盾。所以T是连通且m=n-1的图。,(3)证明由第(2)条可推出第(3)条。首先证明T无圈。对n作归纳证明。n=1时,m=n-1=0,显然无圈。假设结点数为n-1时无圈,今考察结点数是n的情况。此时至少有一个结点v其度数deg(v)=1。我们删去v及其关联边得到新
5、图T,根据归纳假设T无圈,再加回v及其关联边又得到图T,则T也无圈。其次,若在连通图T中增加一条新边(vi,vj),则由于T中由vi到vj存在一条通路,故必有一个圈通过vi,vj。若这样的圈有两个，则去掉(vi,vj),T中必存在通过vi,vj的圈，与T无圈矛盾。故加上边(vi,vj)得到一个切仅一个圈。,(4)证明由第(3)条可推出第(4)条。若图不连通,则存在两个结点vi和vj,在vi和vj之间没有路,若加边(vi,vj)不会产生简单回路（圈）,但这与假设矛盾。由于T无圈,所以删去任一边,图便不连通。(5)证明由第(4)条可推出第(5)条。由连通性知,任两点间有一条路径,于是有一条通路。若
6、此通路不唯一,则T中含有简单回路,删去此回路上任一边,图仍连通,这与假设不符,所以通路是唯一的。,(6)证明由第(5)条可推出树的定义。显然连通。若有圈,则圈上任意两点间有两条通路,此与通路的唯一性矛盾。证毕。由定理7.5.2所刻画的树的特征可见：在结点数给定的所有图中，树是边数最少的连通图，也是边数最多的无圈图。由此可知，在一个（n，m）图G中，若mn1，则G是不连通的；若mn1，则G必定有圈。,【例7.5.2】T是一棵树,有两个2度结点，一个3度结点，三个 4度结点，T有几片树叶？解：设树T有x片树叶，则T的结点数 n=2+1+3+x T的边数 m=n-1=5+x 又由 得 2（5+x）=
7、22+31+43+x 所以x=9，即树T有9片树叶。,7.5.2无向图中的生成树与最小生成树(Spanning Trees and Minimal Spanning Trees)定义7.5.2 若无向(连通图)G的生成子图是一棵树，则称该树是G的生成树，记为TG。生成树TG中的边称为树枝。图G中其它边称为TG的弦。所有这些弦的集合称为TG的补。如图7.5.3中(b)、(c)所示的树T1、T2是(a)图的生成树，而(d)所示的树T3不是(a)图的生成树。一般的，图的生成树不唯一。,图 7.5.3,考虑生成树T1，可知e1，e2，e3，e4是T1的树枝，e5，e6，e7是T1的弦，集合e5，e6，
8、e7是T1的补。生成树有其一定的实际意义。【例7.5.3】某地要兴建个工厂，拟修筑道路连接这处。经勘测其道路可依如图7.5.3(a)图的无向边铺设。为使这处都有道路相通，问至少要铺几条路？解 这实际上是求G的生成树的边数问题。一般情况下，设连通图G有n个结点，m条边。由树的性质知，T有n个结点，n1条树枝，mn1条弦。在图7.5.3(a)中，n5，则n1514，所以至少要修条路才行。,定义7.5.3 设GV,E是一连通的有权图，则G的生成树TG为带权生成树,TG的树枝所带权之和称为生成树TG的权,记为C(TG)。G中具有最小权的生成树TG称为G的最小生成树。求最小生成树问题是有实际意义的。如要
9、建造一个连接若干城市的铁路网络，已知城市vi和vj之间直达铁路的造价，设计一个总造价为最小的铁路网络，就是求最小生成树TG。下面介绍求TG的克鲁斯克尔（Kruskal)算法。,此方法又称为“避圈法”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤如下：1)在G中选取最小权边，置边数i1。2)当in1时，结束。否则，转3)。3)设已选择边为 e1,e2,ei，在G中选取不同于e1,e2,ei 的边 ei+1,使 e1,e2,ei,ei+1无圈且ei+1是满足此条件的最小权边。4)置i为i1，转2)。,【例7.5.4】求图7.5.4(0)中有权图的最小生成树。解:因为 图中n8，所以按算
10、法要执行n17次，其过程见图7.5.4中(1)(7)。,图 7.5.4,【例7.5.5】求图7.5.5中有权图G的最小生成树。解:因为 图中n8，所以按算法要执行n17次。,图 7.5.5,【例7.5.6】图7.5.6所示的赋权图G表示七个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。,图7.5.6,解:该问题相当于求图的最小生成树问题，此图的最小生成树为图7.5.6中的TG,因此如图TG架线使各城市间能够通讯，且总造价最小，最小造价为：()2348,小结：本节介绍了树、生成树和最小生成树的概念、树的六种等价定义及最小生成树的求法。重点:掌握六种等价定义及最小生成树的求法。作业:P327(2),(3),(6),
