1、1n 主要内容q 无 向树及其性质q 生成树q 根树及其 应用第十六章 树216.1 无向树及其性质定义 16.1 (1) 无向树 连通无回路的无向图(2) 平凡树 平凡图(3) 森林 至少由两个连通分支（每个都是树）组成(4) 树叶 1 度顶点(5) 分支点 度数 2的顶点3无向树的等价定义定理 16.1 设 G=是 n阶 m条边的无向图，则下面各命题是等价的：(1) G 是树(2) G 中任意两个顶点之间存在惟一的路径 .(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1.(5) G 是连通的且 G 中任何边均为桥 .(6) G 中没有回路，但在任何两个不同的顶点之间加一
2、条新边，在所得图中得到惟一的一个含新边的圈 . 4(3)(4). 只需证明 G连通 . 用反证法 . 否则 G有 s（ s2）个 连通分支 都是小树 . 于是有 mi=ni1, ，这与 m=n1矛盾 . 证明思路(2)(3). 若 G中有回路，则回路上任意两点之间的路径不惟一 . 对 n用归纳法证明 m=n1. n=1正确 . 设 nk时对，证 n=k+1时也对：取 G中边 e，Ge有且仅有两个连通分支 G1,G2(为什么 ?) . nik，由归纳假设得 mi=ni1, i=1,2. 于是， m=m1+m2+1=n1+n22+1=n1.(1)(2). 关键一步是 , 若路径不惟一必有回路 .
3、5(4)(5). 只需证明 G 中每条边都是桥 . 为此只需证明命题“G 是 n 阶 m 条边的无向连通图，则 mn1”. 命题的证明 : 对 n归纳 . eE, Ge只有 n2条边，由命题可知 Ge不连通，故 e为桥 . 证明思路(5)(6). 由 (5)易知 G为树，由 (1)(2)知， u,vV（ uv） , u到 v有惟一路径，加新边 (u,v)得惟一的一个圈 . (6)(1). 只需证明 G连通，这是显然的 . 6由上式解出 x 2. 定理 16.2 设 T是 n阶非平凡的无向树，则 T 中至少有两片树叶 . 无向树的性质证 设 T 有 x 片树叶，由握手定理及定理 16.1可知，7
4、实例例 1 已知无向树 T中 , 有 1个 3度顶点 , 2个 2度顶点 , 其余顶点全是树叶 . 试求树叶数 , 并画出满足要求的非同构的无向树 . 解 设有 x片树叶 ,2(2+x)=13+22+x解得 x=3， 故 T有 3片树叶 .T的度数列为 1, 1, 1, 2, 2, 38实例例 2 画出所有 6阶非同构的无向树解 5条边 , 总度数等于 10可能的度数列 :(1) 1,1,1,1,1,5(2) 1,1,1,1,2,4(3) 1,1,1,1,3,3(4) 1,1,1,2,2,3(5) 1,1,2,2,2,2(1) (2) (3)(4a) (4b) (5)9不一定连通，也不一定不含
5、回路，如图所示定义 16.2 设 G为无向图(1) G的 树 T 是 G 的子图并且是树(2) G的 生成树 T 是 G 的生成子图并且是树(3) 生成树 T的 树枝 T 中的边(4) 生成树 T的 弦 不在 T 中的边(5) 生成树 T的 余树 全体弦组成的集合的导出子图16.2 生成树10生成树的存在性定理 16.3 任何无向连通图都有生成树 .证 用破圈法 . 若图中无圈 , 则图本身就是自己的生成树 . 否则删去圈上的任一条边 , 不破坏连通性 , 重复进行直到无圈为止 , 得到图的一棵生成树 .推论 1 设 n阶无向连通图有 m条边 , 则 mn1. 推论 2 设 n阶无向连通图有 m条边 , 则它的生成树的余树有 mn+1条边 .
