第9章树 ■91无向树及生成树 ■92根树及其应用
1 第9章 树 ◼ 9.1 无向树及生成树 ◼ 9.2 根树及其应用
91无向树及生成树 无向树、森林 树枝、弦、余树 生成树 ■基本回路与基本回路系统 ■基本割集与基本割集系统 最小生成树
2 9.1 无向树及生成树 ▪ 无向树、森林 ▪ 树枝、弦、余树 ▪ 生成树 ▪ 基本回路与基本回路系统 ▪ 基本割集与基本割集系统 ▪ 最小生成树
无向树 无向树:连通无回路的无向图 平凡树:平凡图 森林:每个连通分支都是树的非连通的无向图 树叶:树中度数为1的顶点 分支点:树中度数≥2的顶点 右图为一棵12阶树 声明:本章中所讨论的回路均 指简单回路或初级回路
3 无向树 无向树: 连通无回路的无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数2的顶点 右图为一棵12阶树. 声明:本章中所讨论的回路均 指简单回路或初级回路
无向树的性质 定理91设G=是n阶m条边的无向图,则下面 各命题是等价的 (1)G是树(连通无回路); (2)G中任意两个顶点之间存在惟一的路径; (3)G中无回路且m=n-1; (4)G是连通的且m=n-1; (5)G是连通的且G中任何边均为桥 (6)G中没有回路,但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈
4 无向树的性质 定理9.1 设G=是n阶m条边的无向图，则下面 各命题是等价的： （1）G是树(连通无回路); （2）G中任意两个顶点之间存在惟一的路径; （3）G中无回路且m=n−1; （4）G是连通的且m=n−1; （5）G是连通的且G中任何边均为桥; （6）G中没有回路, 但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈
无向树的性质(续) 定理92设T是n阶非平凡的无向树,则P中至少 有两片树叶 证设T有x片树叶,由握手定理及定理91可知, (-1)=∑()≥x+2(n-x) 由上式解出x≥2
5 无向树的性质(续) 2(n 1) d(v ) x 2(n x) − = i + − 定理9.2 设T 是 n 阶非平凡的无向树，则T中至少 有两片树叶. 证 设T有x片树叶，由握手定理及定理9.1可知， 由上式解出x2
例题 例1已知无向树?中,有1个3度顶点,2个2度顶点,其余顶点全 是树叶试求树叶数,并画出满足要求的非同构的无向树. 解用树的性质m=n-1和握手定理 设有x片树叶,于是m=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棵非同构的无向树,如图所示
6 例题 例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全 是树叶.试求树叶数,并画出满足要求的非同构的无向树. 解 用树的性质m=n−1和握手定理. 设有x片树叶，于是n=1+2+x=3+x, 2m=2(n−1)=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,并画出满足要求的所有非同构 的无向树. 解设T的阶数为n,则边数为n1,4度顶点的个数为n-7.由握 手定理得 2m=2(n-1)=5×1+2×1+3×1+4(-7) 解出n=8,4度顶点为1个 T的度数列为1,1,1,1,1,2,3 有3棵非同构的无向树
7 例题 例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点 的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构 的无向树. 解 设T的阶数为n, 则边数为n−1, 4度顶点的个数为n−7. 由握 手定理得 2m=2(n−1)=51+21+31+4(n−7) 解出n=8, 4度顶点为1个. T的度数列为1,1,1,1,1,2,3,4 有3棵非同构的无向树
生成树 设G为无向连通图 G的生成树:G的生成子图并且是树 生成树T的树枝:G在T中的边 生成树T的弦:G不在T中的边 生成树T的余树T:所有弦的集合的导出子图 注意:T不一定连通,也不一定不含回路 右图黑边构成生成树 红边构成余树
8 生成树 T T 设G为无向连通图 G的生成树: G的生成子图并且是树 生成树T的树枝: G在T中的边 生成树T的弦: G不在T中的边 生成树T的余树 : 所有弦的集合的导出子图 注意： 不一定连通, 也不一定不含回路. 右图黑边构成生成树 红边构成余树
生成树的存在性 定理任何无向连通图都有生成树. 证用破圈法若图中无圈,则图本身就是自己的生成树 否则删去圈上的任一条边,这不破坏连通性,重复进行 直到无圈为止,剩下的图是一棵生成树 推论1设m阶无向连通图有m条边,则m≥n-1. 推论2设m阶无向连通图有m条边,则它的生成树的余树 有mn+1条边 推论3设T为G的生成树T的余树,C为G中任意 个圈,则C与T一定有公共边
9 生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法.若图中无圈,则图本身就是自己的生成树. 否则删去圈上的任一条边,这不破坏连通性,重复进行 直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边,则mn−1. 推论2 设n阶无向连通图有m条边,则它的生成树的余树 有m−n+1条边. 推论3 设 为G的生成树T 的余树，C 为G 中任意一 个圈，则C与 一定有公共边. T T
基本回路与基本回路系统 定义设T是n阶m条边的无向连通图G的一棵生成 树,设e1,2,…,m为T的弦设C为T添加弦e 产生的G中惟一的圈(由e和树枝组成,称C为对应 弦E的基本回路或基本圈,r=1,2,…,m-n+1.称{C1, C2,…,Cmn+为对应T的基本回路系统 求基本回路的算法:设弦e=(n,吵),先求T中u到v的路径 C,再并上弦e即得对应e的基本回路. 10
10 基本回路与基本回路系统 定义 设T是n阶m条边的无向连通图G的一棵生成 树，设e1 , e2 , … , e m−n+1为T的弦. 设Cr为T添加弦er 产生的G中惟一的圈(由er 和树枝组成), 称Cr为对应 弦er 的基本回路或基本圈,r=1, 2, …, m−n+1. 称{C1 , C2 , …, Cm−n+1 }为对应T的基本回路系统. 求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径 uv, 再并上弦e, 即得对应e的基本回路