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