section3.3.ppt

3 3最优生成树一 模型提出与转化为了给一些乡村联合供水 必须在各村之间建立管线系统 则我们在设计规划的时候就要考虑经济和其他的因素 特别需要考虑的一点是要求管线系统的总造价最少 我们用边上的权表示从村到村的管线的费用 就可以得到一个赋权图 那么上述问题就转化为在一个赋权图中找出具有最小权的连通生成子图 由于权表示造价 当然是非负的 所以这个有最小权的连通生成子图必不含回路 即是图的一棵生成树 定义3 3 1连通赋权图中具有最小权的生成树称为最优生成树 简称最优树 这样要设计一个总造价最小的管线系统 就归结为在连通赋权图中找最优树 二 模型解决 这里提供了解决这个问题的一个算法 Kruskal算法 1956年 克拉斯科 Kruskal 给出了在连通赋权图中求解最优生成树的算法提 这个算法称为Kruskal算法 其基本思路就采用第二节中的避圈法 三 实践操作 考察下图赋权图 其中顶点表示水源 用水的乡村为 水管只许沿着图的边敷设 边旁侧的数字表示对应水管的建设费用 以10000个货币单位 下面使用Kruskal算法解决实际问题 定理3 3 1由Kruskal算法构造的任何生成树都是的最优生成树 不在中 则是含有条边的连通图 因此也是的生成树 易得 选取的一棵最优树 使最大 设 则同时在中和中 但不在中 由定理3 1 2 5 知包含惟一的一个回路 记为 则中至少有一条边设为不在中 取 证明 前面已经说明了是的生成树 若不是的最优生成树 对的任何异于的生成树 定义的函数如下 与选取相矛盾 因此是的最优生成树 所以也是的一棵最优树 然而 由于 我们有 结合 1 和 2 有 由于Kruskal算法中选取的边 是使为无回路图的权最小的边 而是的子图 它也是无回路图 于是可得 四 破圈法 设是连通赋权图 若不是树 则中必有回路 我们删去中含于某回路内权最大的一条边 所得图记为 是的连通生成图 下一步 若不是树 又从的某回路内删去权最大的一条边 如此下去 最后不能按上述方式删边时 得到的图便是的一棵最优生成树 下图是利用破圈法由 a 到 f 得到最优生成树 问题 考察图G的下面两棵最优树 下图两棵生成树中 哪棵结构更加稳定 从直观上分析 从理论上分析 以输电系统为例 将最稳定的最优生成树称为最小流量的最优生成树 我们以顶点7作为实际管线系统的中心 在最优生成树中 若顶点4发生断路时 对应的顶点3 2 1都受到影响 在最优生成树中 若顶点4发生断路 对应的只有顶点3受到影响 同样可以考虑顶点3发生断路时 其它顶点受到的影响 由此从结构上看 的稳定性比要好 首先 输电网络系统转化为双赋权图 输电系统规划区内用电部门 作为双赋权图的顶点 记作 将这些顶点间可能架设的线路称为整个输电网络的边 记作 将边上的建设总费用 包括线路材料费和施工费用 与运行费用 主要为损失 之和称作边的权 将顶点对应用电部门的用电量称做顶点的权 这样就将供电系统网络转化为一个双赋权图 其中V和E分别表示图中所有顶点和边的集合 对于一棵生成树T 顶点的影响因子表示的是该顶点断路时对整个系统产生的影响大小 顶点的影响因子为该顶点的后续顶点的权和 即若记顶点有t个后续顶点 后续顶点的权分别为 则顶点的影响因子为 通过影响因子的大小可以来判断同一个无向图的所有最优生成树的稳定性大小 影响因子越大 则稳定性越低 影响因子越小 则稳定性越高 定义2G是一个简单图 图G的全部最优生成树为 则对 不妨设为生成树的根 在输电系统中 为电厂所在位置 则对 生成树中 顶点的影响因子分别为 则树中所有顶点的影响因子和为 称为的影响因子 若其对应的最优生成树称为最小流量最优生成树 定理设为双赋权图 以为根的最优生成树中 的层数为0 权为 顶点的层数为1 权分别为 顶点的层数为2 权分别为 顶点的层数为 权分别为 则最优生成树的影响因子为 由以上定义及定理 得出求最小流量最优生成树的算法如下 第一步 给定一无向连通图 对于G中的每条边都赋权 用破圈法求G的一棵最优生成树 第二步 用约化原则求解图的所有最优生成树 第三步 若以为根的最优生成树 的层数为0 权为 顶点的层数为1 权分别为 顶点的层数为2 权分别为 顶点的层数为 权分别为 则最优生成树的影响因子为 给出求最小流量的最优生成树算法前 先给出约化原则的算法 选取一棵最小生成树 求出的全部基本回路 只包含中一条边的割集 对每一个基本回路去掉唯一最长边 约化所给的图 然后对应于的每条树边 求出基本割集 若此树边也是基本割集中唯一最短边 则取其为固定边 并将此基本割集作上记号 求其他的最小生成树时 就不用考虑此割集了 其余的基本割集 应用递推关系 对应于递推式求出所有的换入边 对于距离为1的 每一个换入边对应着一棵最小生成树 对于距离为2的每两个换入边也对应着一棵最小生成树 换入k条边 就对应着距离为k的最小生成树 以此类推就可以求出全部的最小生成树 例2如下图所示 无向图是一个输电网络双赋权图 图G中顶点7为电厂所在的位置 求图G最小流量的最优生成树 解 第一步 运用破圈法 首先求出G的其中一棵最优生成树 第二步 利用约化原则 求出G的约化图 在约化图基础上求出G的全部最优生成树分别为 最优树 第三步 利用定