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

* 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 一个连通无圈无向图称为无向树(简称为树)。 记作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中至少有两片树叶。证毕。 定理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, 于是 得出矛盾。所以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中含有简单回路,删去此回路上任一边,图仍连通,这与假设不符,所以通路是唯一的。