第10章图论(续1).pptVIP

第2节 树 运筹学 （第三版） 《运筹学》教材编写 组 第10章 图与网络优化  清华大学出版社 2.1树及其性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。 　已知有五个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话（允许通过其它城市），并且电话线的根数最少。 　不含圈的连通图 定义1 一个无圈的连通图叫做树。 下面介绍树的一些重要性质： 定理3 设图G=（V，E）是一个树P(G) ≥2，那么图G中至少有两个悬挂点。 定理4 图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有P-1条边。 定理5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有P-1条边。 定理8.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。 从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。 （2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。 2.2图的支撑树 定义2 设图T=(V,E’)是图G=(V,E)的支撑子图,如果图T=(V,E’)是一个树,那么称T是G的一个支撑树。 若T=（V，E′）是图 G=（V，E）的支撑树，则T的边数： q(T)= p(T)-1= p(G)-1， G 中不属于 T 的边数是 q(G)-（p(G)-1）= q(G)-p(G)+1 。 定理 7 图G有支撑树的充分必要条件是 G 连通。 必要性显然。 充分性 设G连通。若G是树，则G是它自己的支撑树。若G非树，则 G含圈，从该圈中任意去掉一边，得G的支撑子图G′，若G′为树，则是G的支撑树；若 G ′非树，则G ′含圈，又去掉圈中任意一条边，如此反复进行，因边数有限，最后必得G的一个支撑树。证毕！ 上定理的证明过程实际上给出了寻找一个图的支撑树的一个方法，名“破圈 法”，就是任取图中一个圈，去掉圈中一条边，如此反复进行直到获得一个 支撑树为止。 例6:用破圈法求出图的一个支撑树 　取一个圈(v1,v2,v3,v1)，在一个圈中去 掉边e3 。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4 。再从圈（v3,v4 v5,v3）中去掉边e6 。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边e8，这样，剩下的图不含圈，于是得到一个支撑树。 例6:用避圈法求出图的一个支撑树 2.3 最小支撑树 定义 3 给图G=（V，E）的每一条边[Vi，Vj]赋予一个实数Wij, 则称G 为 赋权图。而Wij称为边 [Vi，Vj] 的权。 定义 4 如果T=（V，E′）是赋权图G 的一个支撑树，称T的所有边的权数之和为T的权，记为w(T). 如果图G的支撑树T*的权w(T*)是G的所有支撑树中权为最小的支撑树，则称T*为G的最小支撑树，简称最小树。 1、 “避圈法”生长法 Kruskal 2、 “破圈法” * v2 v3 v5 v4 v1 v6 v5 v2 v3 v4 v1 图10－14 a v6 v2 v4 v1 b v3 v5 V5 V4 V2 V3 V1 e6 e5 e4 e3 e2 e1 e8 e7 v3 v2 e1 e2 e5 e7 v1 v4 v5 V1 V2 V3 V4 V5 V6 e1 e2 e3 e4 e5 e6 e7 e8 e9 v6 v5 v2 v3 v4 (a) v1 6 2 7 5 3 5 4 4 v3 v2 v1 v4 v6 v5 5 1 3 1 4 2 (b) v6 v5 v2 v3 v4 (a) v1 6 2 7 5 3 5 4 4 1 (b) v3 v2 v1 v4 v6 v5 5 3 1 4 2 2.3 最小支撑树问题 定义 3 给图G=（V，E）的每一条边[Vi，Vj]赋予一个实 数Wij, 则称G 为 赋权图。 而Wij称为边 [Vi，Vj] 的权。 此处所谓权，是关于边的数量指标，其意义视实际请况而定。 定义 4 如果T=（V，E′）是赋权图G 的一个支撑树，称T的所 有 边的权数之和为T的权，记为w(T). 定义 5 如果图G的支撑树T*的权w(T*)是G的所有支撑树中权为 最小的支撑树，则称T*为G的最小支撑树，简称最小树。 w(T*)= m i n w