资源描述：
《离散数学(7.7树与生成树)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、7.5树与生成树(TreesandSpanningTrees)7.5.1无向树(UndirectedTrees)7.5.2无向图中的生成树与最小生成树(SpanningTreesandMinimalSpanningTrees)7.5.1无向树(UndirectedTrees)树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中Ｃ2H2n+2的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。定
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，有若T中的无树叶，则T中每个顶点的度数≥2,则Σdeg(vi)≥2n,（2）若T中只有一片树叶
3、，则T中只有一个结点度数为1,其它结点度数≥2,所以(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无
4、圈。下证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,边
5、数分别为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及其关联边得到新图T′,根据归纳假设T′无圈,再加回v及其关联边又得到图T,则T也无圈。其次,若在连通图T中增加一条新边(vi,vj),则由于T中由vi到vj存在一条通路,故必有一个圈通过vi,vj。若这样的圈有两个，则去掉(v
6、i,vj),T中必存在通过vi,vj的圈，与T无圈矛盾。故加上边(vi,vj)得到一个切仅一个圈。(4)证明由第(3)条可推出第(4)条。若图不连通,则存在两个结点vi和vj,在vi和vj之间没有路,若加边(vi,vj)不会产生简单回路（圈）,但这与假设矛盾。由于T无圈,所以删去任一边,图便不连通。(5)证明由第(4)条可推出第(5)条。由连通性知,任两点间有一条路径,于是有一条通路。若此通路不唯一,则T中含有简单回路,删去此回路上任一边,图仍连通,这与假设不符,所以通路是唯一的。(6)证明由第(5)条可推出
7、树的定义。显然连通。若有圈,则圈上任意两点间有两条通路,此与通路的唯一性矛盾。证毕。由定理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+xT的边数m=n-1=5+x又由得2·（5+x）=2·2+3·1+4·3+x所以x=9，即树T有
8、9片树叶。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)图的生成树。一
