运筹学_树[精选].pptVIP

第六章 图与网络分析 一、树的概念和性质 2-2、图的最小支撑树 (最小部分树) P152 2-2、图的最小支撑树 (最小部分树) P152 算法2 (避圈法) 算法2 (避圈法) 算法2 (破圈法) 作 业 算法2 (破圈法) 找生成树的两种方法-深探法 找生成树的两种方法-广探法 三、最小生成树问题 算法2 (破圈法) 四、树根及其应用 D A Huffman算法_B 8.9 最优检索问题 8.9 最优检索问题 * §2 树图和图的最小部分树 1、树的性质 2、图的最小部分树 3、最避圈法和破圈法 例5 乒乓球单打比赛抽签后，可用图表示。 无圈的连通图称为树，记作 T (V, E)。树中次为1的称为树叶，次大于1的称为分枝点。 A B C D F G I J K L M N E H 定理 图T=(V, E),|V|=n, |E|=m, 则下列关于树的说法是等价的。 (1) T 是一个树。 (2) T 无圈，且 m = n - 1 。 P152 性质2 (3) T 连通，且 m = n - 1 。 P152 性质3 (4) T 无圈, 但每加一边即得惟一一个圈。 (5) T连通，但任舍去一边就不连通。 (6) T中任意两点有惟一链相连。 树图的边称为树枝, 不在生成树上的边称为弦.如边有权重,树枝总长最小的生成树称为该图的最小支撑树. e1, e2, e3, e7, e8, e9为树枝, 定义15 若图G=(V, E)有生成子图是一棵树, 则称该树为G (a) e6 e3 e4 e2 e5 e1 e9 e8 e7 (b) e7 e3 e2 e1 e 9 e8 (b)为(a)的生成树. e4, e5, e6为弦. 的支撑树 (部分树),。 (c) e6 e4 e5 (c)为(b)的关于(a)的补图. 定理 1 图G=(V, E)中任一点 i , 若 j 是与 i 相邻点中距离最近的，则边[ i, j ]一定必含在该图的最小生成树内. 推论 : 把图的所有点分成V和V，两个集合，则两集合之间连线的最短边一定包含在最小则边[ i, j ]一定必含在该图的最小支撑树内. 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 1 2 3 5 1 2 B A D C S E T min w(T*) = 14 5 7 7 5 4 4 B A D C S E T w(T ) = 32 1.从图中任选一圈； 2. 去掉圈中最大权； 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T 再检查剩余的图，重复1，2.直至无圈为至。 阅读 P151 - p155 P149 6.4(a),(c). 1.从图中任选一棵树； 2.由加上一条弦立即生成一个圈，去掉圈中最大权； 得到一棵新树，重复2. 再检查剩余的弦，直至全部弦检查完毕为至。 5 1 7 7 2 3 5 4 5 1 2 4 B A D C S E T (1) 深探法 ① 在点集V中任取一点v, 给 v 以标号 0 . ②在某点u集已得标号i , 检查一端点为u的各边, 另一 若有(u, w)边之w未标号, 则给w以标号i+1, 记下边(u, w), 若这样的边的另一端均已有标号, 就退到标号为i-1的r 直到全部点得到标号为止。 0 1 2 4 3 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 0 端点是否均已标号。 记下边(u, w). 令w代u, 重复②. 点, 以r 代u ,重复②. 0 1 2 3 4 5 6 7 8 9 10 11 12 1