第3章树
第3章 树
树 连通无回路的无向图称为无向树简称树常用T表 示树。(即树是不包含回路的连通图) 平凡图称为平凡树。 若无向图G至少有两个连通分支则称G为森林。 在无向树中,悬挂顶点称为树叶,度数大于或等 于2的顶点称为分支点
树 连通无回路的无向图称为无向树,简称树,常用T表 示树。(即树是不包含回路的连通图) 平凡图称为平凡树。 若无向图G至少有两个连通分支,则称G为森林。 在无向树中,悬挂顶点称为树叶,度数大于或等 于2的顶点称为分支点
例:判断下列哪些图是树? (b) 解:图)是树,因为它连通又不包含回路。图 (b),(c)不是树,因为图(b)虽连通但有回路,图(c) 虽无回路但不连通。在图(a)中,v1、V4V为 均为叶,v2、v3均为分支节点
例:判断下列哪些图是树? v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v4 v3 v5 (a) (b) (c) 解: 图(a)是树, 因为它连通又不包含回路。图 (b), (c)不是树, 因为图(b)虽连通但有回路, 图(c) 虽无回路但不连通。 在图(a)中, v1、 v4、 v5为 均为叶, v2、 v3均为分支节点
定理:设G=VE是无向图,||=n,|E|=m,则下列 各命题是等价的: ①G是树。 ②G中每一对结点之间存在惟一的路。 ③G中无回路且m=n-1。 ④G是连通的且m=n-1。 ⑤G是连通的且G中任何边均为桥 ⑥G中无回路,但在任何两个不同的结点之间增加 个新边,得到一个惟一的含新边的回路。 证明:④→② G是树,所以G是连通的,Ⅴu∈V,Vv∈V,u和v之 间存在一条路。着路不惟一,设L1和L都是u和V之间的 路,则L和L2组成了G中的一个回路,与G是树矛盾
定理:设G=V,E是无向图,|V|=n,|E|=m,则下列 各命题是等价的: ① G是树。 ② G中每一对结点之间存在惟一的路。 ③ G中无回路且m=n–1。 ④ G是连通的且m=n–1。 ⑤ G是连通的且G中任何边均为桥。 ⑥ G中无回路,但在任何两个不同的结点之间增加一 个新边,得到一个惟一的含新边的回路。 证明:①② G是树,所以G是连通的,uV,vV,u和v之 间存在一条路。若路不惟一,设L1和L2都是u和v之间的 路,则L1和L2组成了G中的一个回路,与G是树矛盾
②→④ 先证G中无回路。若G中存在某个结点上的 自回路,Vu∈V,由条件知到w存在一条路L1 u.,因为ν上有自回路,所以u到存在另一条 路L2:u.w,这与G中每一对结点之间存在惟 的路矛盾。若G中存在长度大于等于2的一条回路 则回路上两个结点之间存在不同的路。这与条件 是矛盾的。所以G中无回路。 以下用归纳法证明m=n-1。 当n=1时,G为平凡图,m=0=1-1=n-1。结 论成立。 设n时,结论成立。下证n=k+1时,结论也
②③ 先证G中无回路。若G中存在某个结点v上的 自回路,uV,由条件知u到v存在一条路L1: u…v,因为v上有自回路,所以u到v存在另一条 路L2:u…vv,这与G中每一对结点之间存在惟一 的路矛盾。若G中存在长度大于等于2的一条回路, 则回路上两个结点之间存在不同的路。这与条件 是矛盾的。所以G中无回路。 以下用归纳法证明m=n–1。 当n=1时,G为平凡图,m=0=1–1=n–1。结 论成立。 设n≤k时,结论成立。下证n=k+1时,结论也 成立
设nk时,结论成立。下证n=k+1时,结论 也成立。 设e=(u,是G中的一条边,由于G中无回 ’G1e(在G删除边所得的子图有两个连 所以 通分支G和G2,设它们的结点数和边数分别为 m1,n1和m2,n2。于是有n1k和n2k,由归纳 假设知 1和 则 m=m1+m2+1=n1-1+n2-1+1=n-1
设n≤k时,结论成立。下证n=k+1时,结论 也成立。 设e=(u,v)是G中的一条边,由于G中无回 路,所以 G-e(在G删除边e所得的子图)有两个连 通分支G1和G2,设它们的结点数和边数分别为: m1,n1和m2,n2。于是有n1≤k和n2≤k,由归纳 假设知:m1 =n1 –1和m2 =n2 -1,则: m=m1+m2+1=n1 -1+n2 -1+1=n-1
③→④只须证明G是连通的。若不然,设G 有2)个连通分支G1,G2,…,G,G中均无 回路,都是树。由①→②→③可知,m=n1 i=1,…。于是mm+m2+…+m1=m1-1+m2-1 +…+nr1=n1+n2+…+nr′=nt,由于仑2,这 与m=n-1矛盾。所以G是连通图。 ④→⑤只须证明G的每一条边均为桥。设e是 的任意边,删除e得子图G1,G中的边数m1=m 1,G1中的结点数n1=n,m1=m-1=n-1-1=n-2=n12 <n1-1,所以G不是连通图,所以e是桥
③④只须证明G是连通的。若不然,设G 有t(t≥2)个连通分支G1,G2,…,Gt,Gi中均无 回路,都是树。由①②③可知,mi =ni –1, i=1,…,t。于是m=m1+m2+…+mt =n1 -1+n2 -1 +…+nt -1=n1+n2+…+nt -t=n–t,由于t≥2,这 与m=n–1矛盾。所以G是连通图。 ④⑤只须证明G的每一条边均为桥。设e是 G的任意边,删除e得子图G1,G1中的边数m1 =m- 1,G1中的结点数n1 =n,m1 =m–1=n-1-1=n-2=n1 -2 <n1 -1,所以G1不是连通图,所以e是桥
⑤→⑥由于G中每一条边均为桥,因而G中无 回路。又因为G连通,所以G是树。由①→② 知,Vu∈V,Vv∈V,,u与吵之间存在一条 惟一的路。在u与ν之间增加一条新边,就得到 G的一条回路,显然这条回路是惟一的。 ⑥→①只须证明G是连通的,Vu∈,Vv∈V, l却,在u与ν之间增加一条新边u,)就产生G 的一个惟一的回路,故结点和结点连通。由 于u与哗任意的,所以G是连通图
⑤⑥由于G中每一条边均为桥,因而G中无 回路。又因为G连通,所以G是树。由①② 知,uV,vV,u≠v,u与v之间存在一条 惟一的路。在u与v之间增加一条新边,就得到 G的一条回路,显然这条回路是惟一的。 ⑥①只须证明G是连通的,uV,vV, u≠v,在u与v之间增加一条新边(u,v)就产生G 的一个惟一的回路,故结点u和结点v连通。由 于u与v是任意的,所以G是连通图
定理:设T是m阶非平凡的无向树,则T中 至少有两片树叶。 证:因为T是非平凡树所以T中每个顶点的度 数都大于等于1,设T有k片树叶,则有(n-k) 个顶点度数大于等于2,由握手定理可知 2m∑d(v;)≥k+2(n-k) 由m=n-1,将此结果代入上式后解得k≥2
定理: 设T是n阶非平凡的无向树,则T中 至少有两片树叶。 证 : 因为T是非平凡树,所以T中每个顶点的度 数都大于等于1, 设T有k片树叶, 则有(n-k) 个顶点度数大于等于2,由握手定理可知 2m=∑d(vi ) ≥ k+2(n-k) 由m=n-1,将此结果代入上式后解得 k ≥ 2
例:画出5阶所有非同构的无向树。 解:设T为5阶无向树则T的边数为4,T的度 序列之和为8,4(T)≤4,δ(T心1,可能的度序 列为: (1)1,1,1,1,4;(2)1,1,1,2,3;(3)1,1,2,2,2: +r
例:画出5阶所有非同构的无向树。 解:设Ti为5阶无向树,则Ti的边数为4, Ti的度 序列之和为8, △(Ti )≤4, (Ti )≥1, 可能的度序 列为: (1) 1,1,1,1,4; (2) 1,1,1,2,3; (3) 1,1,2,2,2; 。 。 。 。 。 。 。 。 。 。 。 。 。 。