9.1-2 离散数学.ppt

1第9章树? 无向树及生成树? 无向树及生成树?无向树、森林?树枝、弦、余树?生成树?基本回路与基本回路系统?基本割集与基本割集系统?最小生成树3无向树无向树: 无回路的连通无向图平凡树: 平凡图森林: 每个连通分支都是树的非连通的无向图树叶: 树中度数为1的顶点分支点: 树中度数?:本章中所讨论的回路均指简单回路或初级回路4无向树的性质定理设G=<V,E>是n阶m条边的无向图,则下面各命题是等价的:(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径;(3)G中无回路且m=n?1;(4)G是连通的且m=n?1;(5)G是连通的且G中任何边均为桥;(6)G中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈. 5无向树的性质(续))(2)()1(2xnxvdni??????定理设T 是n 阶非平凡的无向树,则T中至少有两片树叶. 证设T有x片树叶,由握手定理及前一个定理可知,由上式解出x? 已知无向树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棵非同构的无向树, 如图所示7例题例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棵非同构的无向树8生成树TT设G为无向连通图G的生成树: G的生成子图并且是树生成树T的树枝: G在T中的边生成树T的弦: G不在T中的边生成树T的余树: 所有弦的集合的导出子图注意:不一定连通, 也不一定不含回路. . 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行直到无圈为止,, 则m?n?1. 推论2设n阶无向连通图有m条边, 则它的生成树的余树有m?n+1条边. 推论3设为G的生成树T 的余树,C 为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的基本回路.