重庆邮电大学理学院：《图论及其应用》课程PPT教学课件_第3章 树与最短路

第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是连通的，uV，vV，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上的 自回路，uV，由条件知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是树。由①② 知，uV，vV，u≠v，u与v之间存在一条 惟一的路。在u与v之间增加一条新边，就得到 G的一条回路，显然这条回路是惟一的。 ⑥①只须证明G是连通的，uV，vV， 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; 。 。 。 。 。 。 。 。 。 。 。 。 。 。