例题 例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的基本回路