第九章降低管道,网络成本的,最小树方法.ppt

* 第九章 降低管道网络成本的最小树方法 第一节 引 例 C O D A B 4 10 4 9 5 8 6 13 O: 锅炉房; A,B,C,D: 浴室。 如何架设管道，既保证四个浴室都有蒸汽管道供应，又使管道的的总长度为最短。 树T=（V，E）， p=n， q=m， 则 m=n-1。 边数=点数-1 定义： 无圈的连通图称为树。树一般用T表示。 一、树的概念、 树的性质: 二 、图的生成树 定义 设图T=[V，E’]是图G=（V，E）的生成子图，如果T是一个树，则称T是G的一个生成树。 v1 v3 v2 v4 v5 v6 （a） v3 v1 v2 v4 v5 v6 （b） （b）是（a）的一个生成树。 定理 图G有生成树的充分必要条件是图G是连通的。 证明：必要性是显然的。 充分性： 设G是连通的，如果G不含圈，则G本身是 一个树，从而是它自身的一个生成树。 现设G含图，从圈中任意去掉一条边，得G的一个生成子图G1，如G1不含圈，则G1是G的一个生成树；如G1含圈，则从G1中任取一圈，从圈中再任意去掉一条边，得G的一个生成子图G2，如此重复，终可得G的一个不含圈的生成子图Gk，于是Gk是G的一个生成树。 （一）破圈法 （二）避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。(找到生成树或判定没有生成树) v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 如果生成树T*的权w（T*）是G的所有生成树的权中最小的，则称T*是G的最小生成树（简称最小树）。即 最小树问题，即求网络G的最小生成树。 第二节 找最小生成树破圈法和加边法 若 网络中边( i , j )的权为dij ,则网络的生成树的权为生成树的各边的权的和. C O D A B 10 4 5 6 C O D A B 4 10 4 9 5 8 6 13 C O D A B 4 9 5 6 C O D A B 4 10 4 5 6 （一）避圈法（Kruskal） 思想：在图中取一条最小权的边，以后每一步中，总 从未被选取的边中选一条权最小的边，并使 之与已选取的边不构成圈（每一步中，如果有 两条或两条以上的边都是最小权的边，则从中 任选一条）。 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 v6 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 1 5 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 （二）破圈法 任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 v3 v1 v2 v4 v5 v6 1 5 第三节 应 用 举 例 例1 O:中央控制室;A,B,C,D,E:控制点 电缆线每米10元,挖电缆 沟(深1米,宽0.6米)土方 3元/米3,其他材料和施工 费5元/米,这项工程的预 算至少要多少元? C O D A B 30 40 90 70 70 20 60 110 E 100 80