离散数学(7.7树与生成树)

7.5树与生成树(TreesandSpanningTrees)•7.5.1无向树(UndirectedTrees)•7.5.2无向图中的生成树与最小生成树(SpanningTreesandMinimalSpanningTrees)7.5.1无向树(UndirectedTrees)•树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中Ｃ2H2n+2的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。••定义7.5.1一个连通无圈无向图称为无向树(简称为树)。记作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，有1deg()22(1)22niimnn若T中的无树叶，则T中每个顶点的度数≥2,则Σdeg(vi)≥2n,（2）若T中只有一片树叶，则T中只有一个结点度数为1,其它结点度数≥2,所以1deg()2(1)22niinn(1)(3)(2),(3)都与(1)矛盾。所以T中至少有两片树叶。证毕。定理7.5.1任一树T中,至少有两片树叶(n≥2时)。•定理7.5.2一个无向图（n,m）图T是树,当且仅当下列5条之一成立。(或者说,这5条的任一条都可作为树的定义。)•(1)无圈且m=n-1。•(2)连通且m=n-1。•(3)无圈,但增加任一新边,得到且仅得到一个圈。•(4)连通但删去任一边,图便不连通(n≥2)。•(5)每一对结点间有唯一的一条通路。(n≥2)。••证:(1)证明由树的定义可知T无圈。下证m=n-1。•对n作归纳。•n=1时,m=0,显然m=n-1。•假设n=k时命题成立,现证明n=k+1时也成立。•由于树是连通而无圈,所以至少有一个度数为1的结点v,在T中删去v及其关联边,便得到k个结点的连通无圈图。由归纳假设它有k-1条边。再将顶点v及其关联边加回得到原图T,所以T中含有k+1个顶点和k条边,符合公式m=n-1。•所以树是无圈且m=n-1的图。•(2)证明由第(1)条可推出第(2)条。•用反证法。若图不连通,设T有k个连通分支(k≥2)T1,T2,…,Tk,其结点数分别是n1,n2,…,nk,边数分别为m1,m2,…,mk,11,kkiiiinnmm于是11(1)1kkiiiimmnnkn得出矛盾。所以T是连通且m=n-1的图。•(3)证明由第(2)条可推出第(3)条。•首先证明T无圈。对n作归纳证明。•n=1时,m=n-1=0,显然无圈。•假设结点数为n-1时无圈,今考察结点数是n的情况。此时至少有一个结点v其度数deg(v)=1。我们删去v及其关联边得到新图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)条。•由连通性知,任两点间有一条路径,于是有一条通路。若此通路不唯一,则T中含有简单回路,删去此回路上任一边,图仍连通,这与假设不符,所以通路是唯一的。•(6)证明由第(5)条可推出树的定义。•显然连通。若有圈,则圈上任意两点间有两条通路,此与通路的唯一性矛盾。证毕。•由定理7.5.2所刻画的树的特征可见：在结点数给定的所有图中，树是边数最少的连通图，也是边数最多的无圈图。由此可知，在一个（n，m）图G中，若m＜n－1，则G是不连通的；若m＞n－1，则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）=2·2+3·1+4·3+x•所以x=9，即树T有9片树叶。niivm1)deg(2•7.5.2无向图中的生成树与最小生成树(SpanningTreesandMinimalSpanningTrees)•定义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，e7｝是T1的补。生成树有其一定的实际意义。•【例7.5.3】某地要兴建５个工厂，拟修筑道路连接这５处。经勘测其道路可依如图7.5.3(a)图的无向边铺设。为使这５处都有道路相通，问至少要铺几条路？•解这实际上是求G的生成树的边数问题。•一般情况下，设连通图G有n个结点，m条边。由树的性质知，T有n个结点，n－1条树枝，m－n＋1条弦。•在图7.5.3(a)中，n＝5，则n－1＝5－1＝4，所以至少要修４条路才行。•定义7.5.3设G＝〈V,E〉是一连通的有权图，则G的生成树TG为带权生成树,TG的树枝所带权之和称为生成树TG的权,记为C(TG)。G中具有最小权的生成树TG称为G的最小生成树。•求最小生成树问题是有实际意义的。•如要建造一个连接若干城市的铁路网络，已知城市vi和vj之间直达铁路的造价，设计一个总造价为最小的铁路网络，就是求最小生成树TG。•下面介绍求TG的克鲁斯克尔（Kruskal)算法。•此方法又称为“避圈法”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤如下：•1)在G中选取最小权边，置边数i＝1。•2)当i＝n－1时，结束。否则，转3)。•3)设已选择边为e1,e2,…,ei，在G中选取不同于e1,e2,…,ei的边ei+1,使｛e1,e2,…,ei,ei+1｝无圈且ei+1是满足此条件的最小权边。•4)置i为i＋1，转2)。•【例7.5.4】求图7.5.4(0)中有权图的最小生成树。•解:因为图中n＝8，所以按算法要执行n－1＝7次，其过程见图7.5.4中(1)~(7)。图7.5.4•【例7.5.5】求图7.5.5中有权图G的最小生成树。•解:因为图中n＝8，所以按算法要执行n－1＝7次。图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架线使各城市间能够通讯，且总造价最小，最小造价为：•Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝48••小结：本节介绍了树、生成树和最小生成树的概念、树的六种等价定义及最小生成树的求法。•重点:掌握六种等价定义及最小生成树的求法。•作业:P327(2),(3),(6)•