1、第 7章 树1 7.1 无向树及生成树 7.2 根树及其应用 7.1 无向树及生成树 无向树与森林 生成树与余树 基本回路与基本回路系统 基本割集与基本割集系统 最小生成树与避圈法 2无向树 3无向树 : 无回路的连通无向图平凡树 : 平凡图森林 : 每个连通分支都是树的非连通的无向图树叶 : 树中度数为 1的顶点分支点 : 树中度数 2的顶点右图为一棵 12阶树 . 注 :本章中所讨论的回路均指简单回路或初级回路树的应用4英国数学家凯莱 (Arthur Cayley)于 19世纪中叶研究 饱和碳氢化合 物 CnH2n+2的同分异构体时 提 出树 的 概 念 . 当 n=1,2,3时 , 都只
2、有一棵非同构的树 ; 当 n=4时 , 有 2棵不同构的树 .甲烷 乙烷 丙烷 丁烷 异丁烷无向树的性质 定理 设 G=是 n阶 m条边的无向图 , 则下面各命 题是等价的： (1) G是树 (连通无回路 ); (2) G中任意两个顶点之间存在惟一的路径 ; (3) G中无回路且 m=n1; (4) G是连通的且 m=n1; (5) G是连通的且 G中任何边均为桥 ; (6) G中没有回路 , 但在任何两个不同的顶点之间加 一条新边后所得图中有惟一的一个含新边的圈 .10无向树的性质 (续 ) 6定理 设 T 是 n 阶非平凡的无向树，则 T中至少 有一片树叶 .证 设 T有 x片树叶，由握手
3、定理及定理 9.1可知，2(n 1) d(vi) x 2(n x)由上式解出 x2.例 1 已知无向树 T中 , 有 1个 3度顶点 , 2个 2度顶点 , 其余顶点全 是树叶 . 试求树叶数 , 并画出满足要求的非同构的无向树 .7解 用树的性质 m=n1和握手定理 .设有 x片树叶，于是 n=1+2+x=3+x, 2m=2(2+x)=13+22+x解得 x=3，故 T有 3片树叶 .T的度数列为 1, 1, 1, 2, 2, 3有 2棵非同构的无向树 .例题例 2 已知无向树 T有 5片树叶 , 2度与 3度顶点各 1个 , 其余顶点 的度数均为 4. 求 T的阶数 n, 并画出满足要求的
4、所有非同构的 无向树 .8解 设 T的阶数为 n, 则边数为 n1, 4度顶点的个数为n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解得 n=8, 4度顶点为 1个 .T的度数列为 1,1,1,1,1,2,3,4有 3棵非同构的无向树生成树 9设 G为 无向连通图G的 生成树 : G的生成子图并且是树 生成树 T的 树枝 : G在 T中的边 生成树 T的 弦 : G不在 T中的边生成树 T的 余树 T : 所有弦的集合的导出子图 注意： T 不一定连通 , 也不一定不含回路 .黑边构成生成树红边构成余树生成树的存在性 10定理 任何无向连通图都有生成树 .证 用破圈法 . 若图中无圈 , 则图本身就是自己的生成 树 . 否则删去圈上的任一条边 , 这不破坏连通性 , 重 复进行直到无圈为止 ,剩下的图是一棵生成树 .推论 设 n阶无向连通图有 m条边 , 则 mn1.
