第二十七讲--无向树

《第二十七讲--无向树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二十七讲树第二十七讲树讲授内容：1.无向树无向树，森林树的等价定义基本结论讲授重点：树基本概念，等价定义，最小生成树2.生成树生成树基本回路讲授难点：基本回路与基本割集的关系基本割集基本回路与基本割集的关系3.最小生成树及其求解算法取小法去大法一、无向树一、无向树1.无向树：连通而无简单回路的无向图称为无向树,简称树(tree)1.无向树：连通而无简单回路的无向图称为无向树,简称树树叶(leave)：树中度数为1的顶点。定理1：无向图T是树,当且仅当下列5条之一成立。分枝点(branchedno

2、de)或内部结点：树中度数大于1的顶点。(或者说,这5条的任一条都可作为树的定义。)空树：单一孤立结点称为空树或平凡树(nulltree)(1)无简单回路且m=n-1的图。m：边数,n：顶点数。2.森林(forest):一个无简单回路的无向图，或一个无向图的每个连通分支均是树时,(2)连通且m=n-1的图。树是森林。(3)无简单回路,但增加任一新边,得到且仅得到一条基本回路。(4)连通但删去任一边,图便不连通(n≥2)。(5)每一对顶点间有唯一的一条基本路径(n≥2)。图8.6―1证明思路：6个命

3、题可以循环推出。例如图8.6―1(a)、(b)所示的都是树,(c)所示的是森林。一、无向树一、无向树证明：1)树的定义连通而无简单回路(1)无简单回路且证明：轮转法m=n-1的图对n归纳法树的定义(1)对n作归纳。反证法n=1时,m=0,显然m=n-1。(5)(2)假设n=k时命题成立,即m=n-1。现考察n=k+1时的情况T：N归纳法由于树T是连通而无简单回路,所以T中存在v∈V,(4)(3)使得d(v)=1,在T中删去v及其关联边,便得到k个顶点的连通无简单回路图T‵。T‵有k个顶点，由归纳假

4、设T‵有k-1条边。(再将顶点v及其关联边加回得到原图T)所以,T中含有k+1个顶点和k条边,符合公式m=n-1。所以,树是无简单回路且m=n-1的图。1一、无向树一、无向树2)(1)无简单回路且m=n-1的图(2)连通且m=n-1的图。一个重要结论：用反证法。若图不连通,设T有k个连通分图无向图G=为连通图，若G无简单回(k≥2)T1,T2,…,Tk,路，则必存在v0∈V,使得d(v0)=1其顶点数分别:n1,n2,…,nk,或为：边数分别:m1,m2,…,mk,无向图G=为

5、连通图，则或者存在v0于是∈V,使得d(v0)=1，或者G存在简单回路。kk∑∑nnmmii=,=ii==11kkmmnn=∑∑ii=(1−=−<−)kn1(k>1)ii==11得出矛盾。所以T是连通且m=n-1的图。一、无向树一、无向树3)(2)连通且m=n-1的图(3)无简单回路,但增加任一新边,得到且3)(2)连通且m=n-1的图(3)。仅得到一条基本回路。(a)证T无简单回路，对n作归纳证明。(b)下证增加任一边(vi,vj),得到且仅得到一条基本回路。n=1时,m=n-1=0,显然无简单

6、回路。由于T连通，从vi到vj有一条基本路径，再加上边假设顶点数n=k时无简单回路,(vi,vj)得到一条基本回路.现考察顶点数是n=k+1时的情况T：假设增加一边(vi,vj)得到两条基本回路，则删除此时因T连通且m=n-1=k,T至少有一顶点v使得d(v)=1边(vi,vj)后必有一简单回路，这与T无简单回路相(因为假如T的每个顶点(n个)的次数都≥2,即d(v)≥2,则矛盾。k+1k+12m=∑d(vi)≥∑2=2(k+1)i=1i=1于是有m≥k+1,这与m=k矛盾。)我们删去T中v及其关

7、联边得到新图T′,根据归纳假设T′无简单回路,再加回v及其关联边又得到图T,则T也无简单回路。一、无向树一、无向树4)(3)无简单回路,但增加任一新边,得到且仅得到一条基6)(5)每一对顶点间有唯一的一条基本路径(n≥2)树的定本回路(4)连通但删去任一边,图便不连通(n≥2)。义(连通而无简单回路)。若图不连通,则存在两个顶点vi和vj,在vi和vj之显然连通。若有简单回路,则回路上任两点间有间没有路径,若加边(vi,vj)不会产生基本回路,但这两条基本路径,此与基本路径的唯一性矛盾。证毕。与假

8、设矛盾。¢最小的连通图：删去任一条边，图就不再连通；由于T无简单回路,所以删去任一边,图便不连通。¢最大的无回路图：加上任一条边(不是环也不是平行5)(4)连通但删去任一边,图便不连通(n≥2)(5)每一对顶点边)，图中会产生回路。间有唯一的一条基本路径(n≥2)。1由连通性知,任两点间有一条路径,于是有一条基本742路径。若此基本路径不唯一,则T中含有简单回路,删去5此回路上任一边,图仍连通,这与假设不符,所以通路是8唯一的。9632一、无向树二、生成树3.生成树：给定一个无向图