西安电子科技大学出版社：面向21世纪高等学校计算机类专业系列教材《离散数学》课程教学资源（PPT课件讲稿）第9章 树

第9章树 第9章树 9,1无向树 9,2根树及其应用 93例题选解 习题九 dBac

第9章 树 第9章 树 9.1 无向树 9.2 根树及其应用 9.3 例题选解 习 题 九

第9章树 91无向树 定义91.1连通无回路的无向图称为无向树,简称 树,记作T。树中的悬挂点称为树叶,其余顶点称为分 支点。每个连通分支均为树的无向图称为森林。平凡 图称为平凡树 例91.1图91.1中(a)、(b)均是树,图(c)是 森林。 由于树无环且无重边(否则有回路),所以树必 是简单图。下面我们来讨论树的性质

第9章 树 9.1 无 向 树 定义9.1.1 连通无回路的无向图称为无向树，简称 树，记作T。树中的悬挂点称为树叶，其余顶点称为分 支点。每个连通分支均为树的无向图称为森林。平凡 图称为平凡树。 例9.1.1 图9.1.1中（a）、（b）均是树，图（c）是 森林。 由于树无环且无重边（否则有回路），所以树必 是简单图。下面我们来讨论树的性质

第9章树 (b) 图911

第9章 树 图 9.1.1 (a) (b) (c)

第9章树 定理91.1无向图T是树,当且仅当以下五条之一成立。 (1)T中无回路且m=n-1,其中m为边数,n为顶点数 (2)T是连通图且m=mn (3)T中无回路,但增一条边,则得到一条且仅一条初 级回路。 (4)T连通且每条边均是桥。 (5)每对顶点间有唯一的一条初级通路

第9章 树 定理9.1.1 无向图T是树，当且仅当以下五条之一成立。 （1）T中无回路且m=n-1，其中m为边数，n为顶点数。 （2）T是连通图且m=n-1。 （3）T中无回路，但增一条边，则得到一条且仅一条初 级回路。 （4）T连通且每条边均是桥。 （5）每对顶点间有唯一的一条初级通路

第9章树 证明①由树的定义可得(1) 施归纳于顶点数n。当n=1时,m=0,则m=n-1成立 假设当n=k时,m=n-1成立。则当n=H+1时,因为树 是连通的且无回路,所以至少有一个度数为1的顶点v, 从树中删去ν和与它关联的边,则得到k个顶点的树T 根据假设它有k-1条边,现将ν和与它关联的边加到T上 还原成树T,则7有k+1个顶点,k条边,边数比顶点数 少1,故m=n-1成立

第9章 树 证明 ①由树的定义可得（1）。 施归纳于顶点数n。当n=1时，m=0，则m=n-1成立。 假设当n=k时，m=n-1成立。则当n=k+1时，因为树 是连通的且无回路，所以至少有一个度数为1的顶点v， 从树中删去v和与它关联的边，则得到k个顶点的树T′ 。 根据假设它有k-1条边，现将v和与它关联的边加到T′上 还原成树T，则T有k+1个顶点，k条边，边数比顶点数 少1，故m=n-1成立

第9章树 ②由(1)可得(2) 再证反证法,若图7不连通,设有k个连通分支T1, 72,…,T(心2),其顶点数分别为n1,n2,…,nk, 则有 ∑ 边数分别为m1,m2,…,mk,则有 ∑m

第9章 树 ②由（1）可得（2）。 再证反证法，若图T不连通，设T有k个连通分支T1， T2，…，Tk（k≥2），其顶点数分别为n1，n2，…，nk， 则有 1 k i i n n =  = 边数分别为m1，m2，…，mk，则有 1 k i i m m =  =

第9章树 因此,有 k ∑m=∑(n1-1)=n-k<n 即m<n-1,这与m=n-1矛盾,故T是连通的m=n-1图

第9章 树 因此，有 1 1 ( 1) 1 k k i i i i m m n n k n = = = = − = −  −   即m＜n-1，这与m=n-1矛盾，故T是连通的m=n-1图

第9章树 ③由(2)可得(3) 若T是连通图并有n-1条边。施归纳于顶点数n 当n=2时,m=n-1=1,所以没有回路,如果增加 条边,只能得到唯一的一个回路。 假设n=时,命题成立。则当n=k+1时,因为T是连 通的并有n-1条边,所以每个顶点都有d(ν)≥1,并且 至少有一个顶点v,满足d(v)=1。否则,如果每个 顶点ν都有d(p)≥2,那么必然会有总度数2m≥2n,即 mn,这与条件m=m-1矛盾。因此至少有一个顶点v, 满足d(V)=1

第9章 树 ③ 由（2）可得（3）。 若T是连通图并有n-1条边。施归纳于顶点数n。 当n=2时，m=n-1=1，所以没有回路，如果增加一 条边，只能得到唯一的一个回路。 假设n=k时，命题成立。则当n=k+1时，因为T是连 通的并有n-1条边，所以每个顶点都有d（v）≥1，并且 至少有一个顶点v0，满足d（v0）=1。否则，如果每个 顶点v都有d（v）≥2，那么必然会有总度数2m≥2n，即 m≥n，这与条件m=n-1矛盾。因此至少有一个顶点v0， 满足d（v0）=1

第9章树 删去vo及其关联的边,得到图T,由假设知T无回 路,现将v及其关联的边再加到T,则还原成T,所以T 没有回路。 如果在连通图7中增加一条新边(,v),则(v, )与P中从v到v的一条初级路径构成一个初级回路, 且该回路必定是唯一的,否则当删去新边(v,v)时, T中必有回路,产生矛盾

第9章 树 删去v0及其关联的边，得到图T′ ，由假设知T′无回 路，现将v0及其关联的边再加到T′ ，则还原成T，所以T 没有回路。 如果在连通图T中增加一条新边（vi，vj），则（vi， vj）与T中从vi到vj的一条初级路径构成一个初级回路， 且该回路必定是唯一的，否则当删去新边（vi，vj）时， T中必有回路，产生矛盾

第9章树 ④由(3)可得(4)。 若图7不连通,则存在两个顶点v;和v,在v;,v;之 间没有路径,如果增加边(ν,ν;)不产生回路,这与 (3)矛盾,因此T连通。因为T中无回路,所以删去任 意一条边,图必不连通。故图中每一条边均是桥。 ⑤由(4)可得(5) 由图的连通性可知,任意两个顶点之间都有一条 通路,是初级通路。如果这条初级通路不唯一,则T中 必有回路,删去回路上的任意一条边,图仍连通,与 (4)矛盾。故任意两个顶点之间有唯一一条初级回路

第9章 树 ④由（3）可得（4）。 若图T不连通，则存在两个顶点vi和vj，在vi，vj之 间没有路径，如果增加边（vi，vj）不产生回路，这与 （3）矛盾，因此T连通。因为T中无回路，所以删去任 意一条边，图必不连通。故图中每一条边均是桥。 ⑤由（4）可得（5）。 由图的连通性可知，任意两个顶点之间都有一条 通路，是初级通路。如果这条初级通路不唯一，则T中 必有回路，删去回路上的任意一条边，图仍连通，与 （4）矛盾。故任意两个顶点之间有唯一一条初级回路