第十章树
第十章 树
树的实例
树的实例 a e d c b
10.1树及其性质 定义101(树) 个连通无回路的图称为树,记为T 树中度数为1的顶点称为树叶(悬挂点) 度数大于1的顶点称为分枝点或内点。 不相交的树的全体称为森林 平凡图称为平凡树 图10.1
10.1 树及其性质 定义10.1（树） 一个连通无回路的图称为树，记为T。 树中度数为1的顶点称为树叶（悬挂点）。 度数大于1的顶点称为分枝点或内点。 不相交的树的全体称为森林。 平凡图称为平凡树 图10.1
10.1树及其性质 定理10.1 设图7有n个顶点,有下列6条T是树的等价定义 (1)7是无回路的连通图; (2)T是无回路图,且e=n-l,其中e是边数; (3)T是连通图,且e=n-l; (4)T是无回路图,且在T的任何两个不相邻的顶点之 间添加一边,恰得一条回路(称T为最大无回路图) 5)T是连通图,但删去任一边后,便不连通(称T为 最小连通图)。 (6)T的每一对不同的顶点之间有唯一的一条路
10.1 树及其性质 定理10.1 设图T有n个顶点，有下列6条T是树的等价定义： （1）T是无回路的连通图； （2）T是无回路图，且e=n-1，其中e是边数； （3）T是连通图，且e=n-1； （4） T是无回路图，且在T的任何两个不相邻的顶点之 间添加一边，恰得一条回路（称T为最大无回路图）； （5） T是连通图，但删去任一边后，便不连通（称T为 最小连通图）。 （6） T的每一对不同的顶点之间有唯一的一条路
证明方法: (1)→(2); (2)→(3); (3)→(4); (4)→(5); (5)→(6); (6)→(1);
证明方法： （1）（2）； （2）（3）； （3）（4）； （4）（5）； （5）（6）； （6）（1）；
证明:(1)→(2) 无回路的连通无向图>无回路e=n-1 证明方法:归纳法,以顶点数为归纳交量, 作归约纳证卵 证明:n=l时,e=0,∴e=n-l成立; 设n=k命题成立,当n=k+1时,因树连通 而无回路,所以至少有一个度数为1的顶点 ν,在T中删去ν及其关联边,得k个顶点的 树T由归纳假设,它有k-l条边。∴原图 边数为k-1+1,顶点数为k+1,命题成立。 ∴c=n-l成立。∴树是无回路且e=m-1的图
证明：（1）（2） 无回路的连通无向图=>无回路且e=n-1 /*证明方法：归纳法，以顶点数为归纳变量， 作归纳证明*/ 证明：n=1时，e=0，∴e=n-1成立； 设n=k命题成立，当n=k+1时，因树连通 而无回路，所以至少有一个度数为1的顶点 v，在T中删去v及其关联边，得k个顶点的 树T’，由归纳假设，它有k-1条边。∴原图T 边数为k-1+1, 顶点数为k+1，命题成立。 ∴e=n-1成立。∴树是无回路且e=n-1的图
(2)→(3) 无回路且e=n-1的图>连通且e=n-1的图 证明方法:反证法,证明连通 k个连 ,2,顶点数及边数分别为n1,, kgeIg..g ek 因每个连通分图是无回路连 通图,故符合树的定义,所以e;=n成立 e=n-k,k>1,这与e=n-1前提矛盾 T连通且具有e=n-l的图
（2）（3） 无回路且e=n-1的图=>连通且e=n-1的图 /*证明方法：反证法，证明连通*/ 证明：设T不连通，有k个连通分图T1 ,......, Tk (k≥2)，顶点数及边数分别为 n1 ,…..., nk ,e1 ,…..., ek ,因每个连通分图是无回路连 通图，故符合树的定义，所以ei =ni-1成立。 ∴ e=n-k，k>1, 这与e=n-1前提矛盾 ∴ T连通且具有e=n-1的图
(3)→(4) 连通且e=n-1的图>无回路,但增加一新边, 得到且仅得到一个赵本回 证明方法:分而治之:1)T无回路,2)增加新 边,回路唯一; 证明:1)T无回路,归纳法; 因T是连通,并且e=n-的图,故当n=1时, e=n-l=0,无回路; 设顶点数为n-时无回路。当顶点数为m时 e=n-l;故至少有一个顶点v,使(吵)=1。删去v及 其关连边得图T,则由归纳假设T无回路,再加 回v及关联边得图T,则T也无回路
（3）（4） 连通且e=n-1 的图=>无回路，但增加任一新边， 得到且仅得到一个基本回路 /*证明方法：分而治之：1）T无回路；2）增加新 边，回路唯一；*/ 证明： 1）T无回路，归纳法； 因T是连通, 并且e=n-1的图，故当n=1时， e=n-1=0, 无回路； 设顶点数为n-1时无回路。当顶点数为n时， e=n-1；故至少有一个顶点v，使d(v)=1。删去v及 其关连边得图T’，则由归纳假设T’无回路，再加 回v及关联边得图T，则T也无回路
2)增加新边,回路唯一; 在连通图T中任意取两点vv,因为T 连通所以νν存在一路径,若增加新边 ("p"),则得一回路,且该回路是唯一的 (否则,删去新边,路径中必有回路。)
2）增加新边，回路唯一； 在连通图 T 中 ,任意取两点 v i, vj ,因为 T 连通所以 v i, vj存在一路径，若增加新边 (v i, vj )，则得一回路，且该回路是唯一的 ( 否则，删去新边, 路径中必有回路。)
(4)→(5) 无回路,但增加在一新边,得到且仅得 到一个基本回路→>连通,但删去在一边 图便不连通。mn>=2 连通的证明方法 证:若图不连通,则存在顶点和v 使v间没有路,增加边{v"下不产生 回路,与前提矛盾。 因T无回路,故删去任一边,图便不 连通
（4）（5） 无回路，但增加任一新边，得到且仅得 到一个基本回路=>连通，但删去任一边， 图便不连通。(n>=2) /*连通的证明方法*/ 证：若图不连通，则存在顶点vi和vj， 使vi, vj之间没有路，增加边{ vi, vj }不产生 回路，与前提矛盾。 因T无回路，故删去任一边，图便不 连通