第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成立