图与网络优化.ppt

图与网络优化 实验十二 通信联络网的建立 例1要在这六个居民点之间设置通信线路网 以保证居民点的联络 每条边代表两居民点的道路 数字代表路长 问如何建立该通信网 使联网代价最小 基本概念和名词图 由若干个不同的点 顶点或节点 与其中某些顶点的连线所组成的图形权 图中的每条边都有一个具体的数与之对应 这些数为权 带权的图为赋权图或网络 边与弧 两点之间不带箭头的连线称为边 带箭头的连线称为弧 无向图 一个图G是由顶点和边构成的 有向图 一个图G是由顶点和弧构成的 V和E分别是图的顶点的集合和边的集合 V v1 v2 vn E e1 e2 em 链 在无向图中 点与边的交错序列 vi1 ei1 vi2 vik 1 eik 1 vik 称为连结vi1和vik的链 eit为连结vit和vit 1的边 路径 vi1 ai1 vi2 vik 1 aik 1 vik 是有向图中一条链 ait为从vit指向vit 1的弧 称之为从vi1到vik的路径 弧的集合 A a1 a2 am 回路 闭合的路径称为回路 圈 闭合的链称为圈 连通图 图G中任何两个点之间至少有一条链 称G为连通图 树 一个无圈的连通图称为树生成树 若G1 V1 E1 是连通图G2 V2 E2 的生成子图 即V1 V2 E1 E2 且G1本身是树 则称G1为G2的生成树 邻接矩阵 bij表示图G中从顶点vi到vj的弧 无向图只考虑vi与vj间的边 的数目 则矩阵B bij 称为图G的邻接矩阵 带权邻接矩阵 以wij表示网络G中从顶点vi到vj的弧的权 无向网只考虑vi与vj间的边的权 当vi到vj无弧或边时 wij 则矩阵W wij 称为图G的带权邻接矩阵 算法步骤如下 1 把赋权图G中的边按权的非减次序排列 最小生成树 在赋权图G中 求一棵生成树使其总权最小 称此为图G的最小生成树 Kruskal算法思想及步骤 每次添加权尽量小的边 使新的图无圈 直到生成一棵树为止 便得最小生成树 最小生成树与Kruskal算法思想 2 按1 排列的次序检查G中的每一条边 如果这条边与已得到的边不产生圈 则取这一条边为解的一部分 3 若已取到n 1条边 算法终止 此时以V为顶点集 以取到的n 1条边为边集的图即为最小生成树 4 5 最短路径与Dijkstra算法最短路径问题 在赋权有向图G中 求一条总权最小的vi至vj的路径的问题 算法思想 若v1 v2 vi vj vn是图G从v1到vn的最短路径 则它的子路vi vj一定是从vi到vj的最短路径 算法步骤 1 假设网络G有n个顶点 用带权的邻接矩阵W来表示 W i j 表示从顶点vi到vj的弧或边上的权值 不存在弧或边的权值用 表示 S为已求出的从始点vi出发的最短路径的终点集合 初始状态为空集 则从vi出发到图上其余各顶点vk可能达到的最短路径长度的初值为 D k min W i k vk V i 2 选择vj 使得 D j min D k vk V S vj就是当前求得的一条从始点vi出发的最短路径的终点 令S S j 3 修改从vi出发到集合V S上任一顶点vk可达的最短路径长度 若D j W j k D k 则修改D k 为 D k D j W j k 4 重复操作2 3 共n 1次 并记录各最短路径经过的所有顶点 由此得到从始点vi到图上其余各顶点的最短路径是依路径长度递增的序列 v6 v1 v2 v3 v4 v5 5 10 50 10 30 20 60 100 40 例2某公司使用一种设备 此设备在一定年限内随时间推移逐渐损坏 保留此设备的时间越长 每年的维修费就越大 现假设该公司在第一年开始时必须购置一台此设备 假设使用此设备的时间为五年 设备的购买费和维修费如下表 不同使用年限设备的维修费 单位 万元 第一年到第五年的购买价格 单位 万元 问 公司应在哪一年购买一台新设备 使维修费和新设备的购置费的总和最小 解考虑六个点v1 v2 v3 v4 v5 v6 其中vi表示在第i年初要购买新设备 v6是虚设点 表示在第5年底购买新设备 从点vi引出指向点vi 1 vi 2 v6的弧 弧 vi vj 表示第i年年初购进的新设备要使用到第j年的年初 弧 vi vj 上所赋的权为第i年的购置费加上从第i年初到第j年初的维修总费用 比如W 1 4 20 5 7 12 44 万元 如此计算可得到所有权值 见下图 本问题变为在赋