福州大学：《离散数学》课程教学资源（课件讲稿）第十六章 树

第十六章树 ■无向树及其性质 ■生成树 ■根树及其应用

第十六章 树  无向树及其性质  生成树  根树及其应用

16.1无向树及其性质 ■无向树、森林 ■无向树的性质

16.1 无向树及其性质  无向树、森林  无向树的性质

无向树 无向树：连通无回路的无向图 平凡树：平凡图 森林：每个连通分支都是树的非连通的无向图 树叶：树中度数为1的顶点 分支点：树中度数≥2的顶点 右图为一棵12阶树. 声明：本章中所讨论的回路均 指简单回路或初级回路

无向树 无向树: 连通无回路的无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数2的顶点 右图为一棵12阶树. 声明:本章中所讨论的回路均 指简单回路或初级回路

无向树的性质 定理16.1设G=是n阶m条边的无向图，则下面 各命题是等价的： (1)G是树（连通无回路）； (2)G中任意两个顶点之间存在惟一的路径 (3)G中无回路且=n-1; (4)G是连通的且m=n-1; (5)G是连通的且G中任何边均为桥； (6)G中没有回路，但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈

无向树的性质 定理16.1 设G=是n阶m条边的无向图，则下面 各命题是等价的： （1）G是树(连通无回路); （2）G中任意两个顶点之间存在惟一的路径; （3）G中无回路且m=n1; （4）G是连通的且m=n1; （5）G是连通的且G中任何边均为桥; （6）G中没有回路, 但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈

无向树的性质（续） 定理16.2设T是n阶非平凡的无向树，则T中至少 有两片树叶. 证设T有x片树叶，由握手定理及定理16.1可知， 2(n-1)=∑d()2x+2(n-x) 由上式解出x之2

无向树的性质(续) 2(n 1) d(v ) x 2(n x)   i    定理16.2 设T 是 n 阶非平凡的无向树，则T中至少 有两片树叶. 证 设T有x片树叶，由握手定理及定理16.1可知， 由上式解出x2

例题 例1已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全 是树叶.试求树叶数，并画出满足要求的非同构的无向树. 解用树的性质n-1和握手定理。 设有x片树叶，于是n=1+2+x=3+x, 2m=2(n-1)=2×(2+x)=1×3+2x2+x 解出x=3,故T有3片树叶. T的度数列为1,1,1,2,2,3 有2棵非同构的无向树，如图所示

例题 例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全 是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解 用树的性质m=n1和握手定理. 设有x片树叶，于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=13+22+x 解出x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向树, 如图所示

例题 例2已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点 的度数均为4.求T的阶数，并画出满足要求的所有非同构 的无向树 解设T的阶数为n,则边数为n-1,4度顶点的个数为n-7.由握 手定理得 2t=2(n-1)=5×1+2×1+3x1+4(n-7) 解出n=8,4度顶点为1个， T的度数列为1,1,1,1,1,2,3,4 有3棵非同构的无向树 中

例题 例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点 的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构 的无向树. 解 设T的阶数为n, 则边数为n1, 4度顶点的个数为n7. 由握 手定理得 2m=2(n1)=51+21+31+4(n7) 解出n=8, 4度顶点为1个. T的度数列为1,1,1,1,1,2,3,4 有3棵非同构的无向树

16.2 生成树 ■生成树、树枝、弦、余树 ■基本回路与基本回路系统 ■基本割集与基本割集系统 ■最小生成树

16.2 生成树  生成树、树枝、弦、余树  基本回路与基本回路系统  基本割集与基本割集系统  最小生成树

生成树 设G为无向连通图 G的生成树：G的生成子图并且是树 生成树T的树枝：G在T中的边 生成树T的弦：G不在T中的边 生成树T的余树T:所有弦的集合的导出子图 注意：T不一定连通，也不一定不含回路。 右图黑边构成生成树 红边构成余树

生成树 T T 设G为无向连通图 G的生成树: G的生成子图并且是树 生成树T的树枝: G在T中的边 生成树T的弦: G不在T中的边 生成树T的余树 : 所有弦的集合的导出子图 注意： 不一定连通, 也不一定不含回路. 右图黑边构成生成树 红边构成余树

生成树的存在性 定理任何无向连通图都有生成树. 证用破圈法.若图中无圈，则图本身就是自己的生成树 否则删去圈上的任一条边，这不破坏连通性，重复进行 直到无圈为止，剩下的图是一棵生成树. 推论1设n阶无向连通图有m条边，则m2n-1, 推论2设阶无向连通图有m条边，则它的生成树的余树 有m-n+1条边. 推论3设T为G的生成树T的余树，C为G中任意一 个圈，则C与下一定有公共边

生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行 直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边, 则mn1. 推论2 设n阶无向连通图有m条边, 则它的生成树的余树 有mn+1条边. 推论3 设 为G的生成树 T 的余树，C 为G 中任意一 个圈，则C与 一定有公共边. T T