1、9.1 无向树及生成树9.2 根树及其应用 12/60第十章 树与有序树10.1 树的基本概念(一 ) 树的定义(二 ) 树的等价定义3/60例 PeterGodfried Betty AlbertMary Marivin DorisJudy HalDenise Gregory4无向树无向树 : 连通无回路的无向图平凡树 : 平凡图森林 : 每个连通分支都是树的非连通的无向图树叶 : 树中度数为 1的顶点分支点 : 树中度数 2的顶点右图为一棵 12阶树 .声明 :本章中所讨论的回路均指简单回路或初级回路 5/60例 是否为树 ?例 画出所有 5个顶点的树6无向树的性质定理 1 设 G=是 n
2、阶 m条边的无向图，则下面各命题是等价的：（ 1） G是树 (连通无回路 );（ 2） G中任意两个顶点之间存在 惟一 的路径 ;（ 3） G中无回路且 m=n1;（ 4） G是连通的且 m=n1;（ 5） G是连通的且 G中任何边均为桥 ;（ 6） G中没有回路 , 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈 . 7无向树的性质 (续 )定理 2 设 T 是 n 阶非平凡的无向树，则 T中至少有两片树叶 . 证 设 T有 x片树叶，由握手定理及定理 1可知，由上式解出 x2.8/60例 1 已知一棵树有 5个 4度顶点， 3个 3度顶点，3个 2度顶点，问有几个一度
3、顶点？解：设有 x个 1度顶点，则依题意有方程：54+33+32+1x = d(v) =2|E| =2(|V|-1)=2(5+3+3+x-1) x=15例 2 已知无向 树 T有 5片 树 叶 , 2度与 3度 顶 点各 1个 , 其余 顶 点的度数均 为 4. 求 T的 阶 数 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棵非同构的无向 树 910/6010.2 连通图的生成树和带权连通图的最小生成树 (一 ) 生成树(二 ) 基本圈、基本割集(三 ) 生成树与基本圈、基本割集的关系(四 ) 最小生成树(五 ) 避圈法
