离散数学章.ppt

第7章 树及其应用 第7章 树及其应用 7.1 无向树 7.2 根树及其应用 7.1 无向树 7.1.1 无向树的定义及其性质 7.1.2 生成树与基本回路和基本割集 7.1.3 最小生成树 无向树的定义 无向树: 连通无回路的无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数?2的顶点 无向树的性质 定理7.1 设G=V,E是n阶m条边的无向图, 下面各命题是 等价的： (1) G是树(连通无回路); (2) G中任意两个顶点之间存在惟一的路径; (3) G是连通的且m=n?1; (4) G中无回路且m=n?1; (5) G中无回路, 但在任何两个不相邻的顶点之间加一条边 所得图中有惟一的一条初级回路. (6) G是连通的且G中任意一条边均为桥. 定理7.1的证明 (1)?(2) 由连通性, 任意2个顶点之间有一条路径. 又, 假设 某2个顶点之间有2条路径, 则这2条路径可组合成一条回 路, 与树的定义矛盾. (2)?(3) 显然连通, 要证m=n?1. 对n作归纳证明. 当n=1时, 显然m=0, 结论成立. 假设当n?k(k?1)时结论成立, 考虑n=k+1. 任取一条边e= (u,v), 它是u,v之间惟一的通路, 删去e, G被分成2个连通分 支, 设它们分别有n1, n2个顶点和m1, m2条边, n1?k, n2?k. 由归纳假设, m1=n1-1, m2=n2-1, 得m= m1+m2+1= n-1. 定理7.1的证明(续) (3)?(4) 假设有回路, 任取一个回路, 删去回路中的一条边, 所得图仍是连通的. 重复这个做法, 直到没有回路为止, 得 到一棵树, 它有n个顶点m-r条边, r0. 由(1)?(2)?(3), 得 m-r =n-1, 矛盾. (4)?(1) 只需证G连通. 假设G不连通, 有p(p1)个连通分支. 设第k个连通分支有nk个顶点和mk条边, 由(1)?(2)?(3), mk= nk-1. 得到m= n-p, 矛盾. 定理7.1的证明(续) (1)?(5) 由(1)?(2), 任意2个不相邻的顶点之间有一条惟 一的路径, 故在这2个顶点之间添加一条新边, 必得到一条 惟一的初级回路. (5)?(6) 首先, 任意2个不相邻的顶点之间都有一条通路, 否则在它们之间添加一条新边不可能构成回路, 故G连通. 其次, 若删去一条边G仍是连通的, 这条边必在一条回路上, 与G中无回路矛盾. (6)?(1) G中无回路, 否则删去回路上任意条边, G仍连通. 无向树的性质(续) 实例 例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶 点全是树叶. 试求树叶数, 并画出满足要求的非同构的无 向树. 实例 例7.3 画出所有6阶非同构的无向树 生成树 定义7.2 设G是无向连通图, 若G的生成子图T是一棵树, 则 称T是G的生成树. G在T中的边称作T的树枝,不在T中的边 称作T的弦. T的所有弦的集合的导出子图称作T的余树 生成树的存在性 定理7.3 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 不破坏连通性, 重复进行直到 无圈为止, 得到图的一棵生成树. 推论1 设n阶无向连通图有m条边, 则m?n?1. 推论2 设n阶无向连通图有m条边, 则它的生成树的余树 有m?n+1条边. 基本回路与基本回路系统 定义7.3 设G是n阶m条边的无向连通图, T是G的一棵生成 树, e1, e2, … , em?n+1为T的弦. G中仅含T的一条弦er的圈Cr 称作对应弦er的基本回路. 称{C1,C2, …, Cm?n+1}为对应T的 基本回路系统 基本割集与基本割集系统 定义7.4 设T是n阶连通图G的一棵生成树, e1?, e2?, …, e?n?1 为T的树枝，Si是G的只含树枝ei?, 其他边都是弦的割集, 称Si为对应树枝ei?的基本割集. 称{S1, S2, …, Sn?1}为对应T 的基本割集系统 最小生成树 图G的每一条边e附加一个实数w(e), 称作边e的权. 图G连 同附加在边上的权称作带权图, 记作G=V,E,W. 设H是G 的子图, H所有边的权的和称作H的权, 记作W(H). 最小生成树: 带权图权最小的生成树 避圈法 (Kruskal) (1) 将所有非环边按权从小到大排列, 设为e1, e2, …, em (2) 令T = ? (3) For k=1 to m Do 若ek与T 中的边不构成回路, 则将ek加入T 中 实例 例5 求图的一棵最小生成树 7.2 根