有关树的几个等价命题 口设T是简单无向图，下列四个命题等价： (1)T是不包含简单回路的连通图。树的定义 (2)T中任意两点之间有唯一简单通路。 (3)T连通，但删除任意一条边则不再连通。 (4)T不包含简单回路，但在任意不相邻的顶点对之间加一 条边则产生唯一的简单回路。 口备注： ■树是边最少的连通图 ■树是边最多的无简单回路的图
设T是简单无向图，下列四个命题等价： (1) T是不包含简单回路的连通图。//树的定义 (2) T中任意两点之间有唯一简单通路。 (3) T连通，但删除任意一条边则不再连通。 (4) T不包含简单回路，但在任意不相邻的顶点对之间加一 条边则产生唯一的简单回路。 备注： ◼ 树是边最少的连通图 ◼ 树是边最多的无简单回路的图 有关树的几个等价命题
树中边和点的数量关系 设T是树，令n=Vbm=ET,则Fn-I。 口证明.对n进行归纳证明。当n=1,T是平凡树，结论显然成立。 假设当n≤k时结论成立。 若n=k+1。因为T中每条边都是割边，任取e∈ET-{e}含两 个连通分支，设其为T1,T2,并设它们边数分别是m1,m2, 顶点数分别是n1,2,根据归纳假设：m11,m2=21。 注意：n+n2=n,m1+m2=m-1。 ∴.m=m+m2+1=n-1
设T是树，令n=|VT |, m=|ET |, 则m=n-1。 证明. 对n进行归纳证明。当n=1, T是平凡树，结论显然成立。 假设当nk时结论成立。 若n=k+1。因为T中每条边都是割边，任取eET , T-{e}含两 个连通分支，设其为T1 , T2 , 并设它们边数分别是m1 , m2 , 顶点数分别是n1 , n2 , 根据归纳假设：m1=n1 -1, m2=n2 -1。 注意：n1+n2=n, m1+m2=m-1。 m= m1+m2+1=n-1。 树中边和点的数量关系
连通图边数的下限 口顶点数为n（n≥2)的连通图，其边数m2-1。 (对于树，=n-L,“树是边最少的连通图”) 口证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且IVc=n>2。任取veVc,令 G=G-y,设G有@(@≥1)个连通分支G1,G2,,G。,且G的边 数和顶点数分别是m和no 我们有n=n1+n2+..+n。+1,m≥m1+m2+..+m。+o(每个连通 分支中至少有一个顶点在G中与删除的相邻)。 由归纳假设，m≥n-1(=1,2,.w)。 所以：m2m1+m2+..+mo十o之n+n2+..+no0+0=n-1o
顶点数为n（n2）的连通图，其边数mn-1。 (对于树，m=n-1, “树是边最少的连通图”) 证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且|VG |=n>2。任取vVG，令 G’=G-v,设G’有(1)个连通分支G1 ,G2 ,…,G，且Gi的边 数和顶点数分别是mi和ni。 我们有n=n1+n2+…+n +1, mm1+m2+…+m + (每个连通 分支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，mi ni -1(i=1,2,…)。 所以：m m1+m2+…+m +n1+n2+…+n -+=n-1。 连通图边数的下限