第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时，结论也 成立