1、1第七章 树主要内容l 无向树及其性质l 生成树l 根树及其应用27.1 无向树及其性质定义 7.1 (1) 无向树 连通无回路的无向图(2) 平凡树 平凡图(3) 森林 至少由两个连通分支（每个都是树）组成(4) 树叶 1 度顶点(5) 分支点 度数 2的顶点3无向树的等价定义定理 7.1 设 G=是 n阶 m条边的无向图，则下面各命题是等价的：(1) G 是树(2) G 中任意两个顶点之间存在惟一的路径 .(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1.(5) G 是连通的且 G 中任何边均为桥 .(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图
2、中得到惟一的一个含新边的圈 . 4 *定理 7.1证明 (1)(2)证明 : (1)(2)(3)(4)(5)(6)(1)(1) G是树 (连通无回 )(2) G中任何 2顶点之间有唯一路径(1)(2): u,vV, G连通 , u,v之间的短程线是路径 . 如果 u,v之间的路径不唯一 , 则 G中有回路 , 矛盾 !5 *定理 7.1证明 (2)(3)(2) G中任何 2顶点之间有唯一路径(3) G无圈 m=n-1证明 (续 ): (2)(3): 任 2点之间有唯一路径 无圈 (反证 : 有圈 存在 2点 ,它们之间有 2条路径 .)m=n-1(归纳法 ): n=1时 ,m=0. 设 nk时
3、成立 ,当 n=k+1时 , 任选 1边 e, G-e有 2个连通分支 ,m=m1+m2+1=(n1-1)+(n2-1)+1=n1+n2-1 =n-1. m1=n1-1 m2=n2-1e6 *定理 7.1证明 (3)(4)(3) G无圈 m=n-1(4) G连通 m=n-1证明 (续 ): (3)(4): G连通 : 假设 G有 s个连通分支 , 则每个连通分支都是树 , 所以m=m1+m2+ m s=(n1-1)+(n2-1)+(n s-1) =n1+n2+n s-s=n-s=n-1, 所以 s=1.m1=n1-1 m2=n2-1 ms=ns-17 *定理 7.1证明 (4)(5)(4) G
4、连通 m=n-1(5) G极小连通 : 连通 所有边是桥证明 (续 ): (4)(5): 所有边是桥 : eE, G-e是 n阶 (n-2)边图 , 一定不连通 (连通 mn-1), 所以 e是割边 . m=n-1em=n-28 *定理 7.1证明 (5)(6)(5) G极小连通 : 连通 所有边是桥(6) G极大无回 : 无圈 增加任何新边得唯一圈证明 (续 ): (5)(6): 所有边是桥 无圈 . u,vV, G连通 , u,v之间有唯一路径 , 则 (u,v)是唯一的圈 . 9 *定理 7.1证明 (6)(1)(6) G极大无回 : 无圈 增加任何新边得唯一圈(1) G是树 (连通无回 )证明 (续 ): (6)(1): G连通 : u,vV, G(u,v)有唯一的圈 C, C-(u,v)是 u,v之间的路径 . #10由上式解出 x 2. 定理 7.2 设 T是 n阶非平凡的无向树，则 T 中至少有两片树叶 . 无向树的性质证 设 T 有 x 片树叶，由握手定理可知，
