运筹学8图与网络分析.ppt

第八章图与网络分析 主要内容 8 1图与网络的基本知识 8 2树和最小支撑树 8 3最短路问题 8 4最大流问题 8 5最小费用最大流问题 8 6中国邮递员问题 目的要求 1 正确理解图的基本概念与基本定理 掌握用图形与矩阵表示图的方法 2 理解树与最小支撑树的概念及求最小树的算法 理解欧拉图与最优投递路线问题的解法 3 熟练掌握赋权的最短通路问题及其Dijkstra算法 会用逐次逼近法求解带有负权的最短路问题 4 理解最大流问题 掌握求最大流的标号算法 会求网络系统的最大流和最小费用最大流 重点 图的基本概念与基本定理 树和最小支撑树 赋权的最短通路问题的求法 网络系统的最大流和最小费用最大流 8 1图与网络的基本知识 图论是应用非常广泛的运筹学分支 广泛应用于物理学控制论 信息论 工程技术 交通运输 经济管理 电子计算机等各项领域 对于科学研究 市场和社会生活中的许多问题 可以用图论的理论和方法来加以解决 例如 各种通信线路的架设 输油管道的铺设 铁路或者公路交通网络的合理布局等问题 都可以应用图论的方法 简便 快捷地加以解决 回本章目录 随着科学技术的进步 特别是电子计算机技术的发展 图论的理论获得了更进一步的发展 应用更加广泛 如果将复杂的工程系统和管理问题用图的理论加以描述 可以解决许多工程项目和管理决策的最优问题 因此 图论越来越受到工程技术人员和经营管理人员的重视 关于图的第一篇论文是瑞士数学家欧拉 E Euler 在1736年发表的解决 哥尼斯堡 七桥难题的论文 德国的哥尼斯堡城有一条普雷格尔河 河中有两个岛屿 河的两岸和岛屿之间有七座桥相互连接 见图8 1a 当地的居民热衷于这样一个问题 一个漫步者如何能够走过这七座桥 并且每座桥只能走过一次 最终回到原出发地 尽管试验者很多 但是都没有成功 为了寻找答案 1736年欧拉将这个问题抽象成图8 1b所示图形的一笔画问题 哥尼斯堡七桥问题 图8 1a A B C D 哥尼斯堡七桥问题可简化为以下图形 其中的四个顶点都是奇顶点 A B C D 图8 1b 即能否从某一点开始不重复地一笔画出这个图形 最终回到原点 欧拉在他的论文中证明了这是不可能的 因为这个图形中每一个顶点都与奇数条边相连接 不可能将它一笔画出 这就是古典图论中的第一个著名问题 一 图与网络的基本概念 在实际的生产和生活中 人们为了反映事物之间的关系 常常在纸上用点和线来画出各式各样的示意图 例8 1图8 2是我国北京 上海 重庆等十四个城市之间的铁路交通图 这里用点表示城市 用点与点之间的线表示城市之间的铁路线 诸如此类还有城市中的市政管道图 民用航空线图等等 图8 2 例8 2有六支球队进行足球比赛 我们分别用点v1 v6表示这六支球队 它们之间的比赛情况 也可以用图反映出来 已知v1队战胜v2队 v2队战胜v3队 v3队战胜v5队 如此等等 这个胜负情况 可以用图8 3所示的有向图反映出来 图8 3 从以上的几个例子可以看出 我们用点和点之间的线所构成的图 反映实际生产和生活中的某些特定对象之间的特定关系 一般来说 通常用点表示研究对象 用点与点之间的线表示研究对象之间的特定关系 由于在一般情况下 图中的相对位置如何 点与点之间线的长短曲直 对于反映研究对象之间的关系 显得并不重要 因此 图论中的图与几何图 工程图等本质上是不同的 综上所述 图论中的图是由点和点与点之间的线所组成的 通常 我们把点与点之间不带箭头的线叫做边 带箭头的线叫做弧 如果一个图是由点和边所构成的 称为无向图 记作G V E 其中V表示图G中的点集合 E表示图G中的边集合 连接点vi vj V的边记作 vi vj 或者 vj vi 如果一个图是由点和弧所构成的 那么称为它为有向图 记作D V A 其中V表示有向图D的点集合 A表示有向图D的弧集合 一条方向从vi指向vj的弧 记作 vi vj 例如 图8 4是一个无向图G V E 其中V v1 v2 v3 v4 E v1 v2 v2 v1 v2 v3 v3 v4 v1 v4 v2 v4 v3 v3 图8 4 图8 5是一个有向图D V A 其中V v1 v2 v3 v4 v5 v6 v7 A v1 v2 v1 v3 v3 v2 v3 v4 v2 v4 v4 v5 v4 v6 v5 v3 v5 v4 v5 v6 v6 v7 图8 5 下面介绍一些常用的名词 一个无向图G或有向图D中的点数 记作P G 或P D 简记作P 边数或者弧数 记作q G 或者q D 简记作q 如果边 vi vj E 那么称vi vj是边的端点 或者vi vj是相邻的 如果一个图G中 一条边的两个端点是相同的 那么称为这条边是环 如图8 4中的边 v3 v3 是环 如果两个端点之间有两条以上的边 那么称为它们为多重边 如图8 4中的边 v1 v2 v2 v1 一个无环 无多重边的图称为简单图 一个无环 有多重边的图称为多重图 以点v为端点的边的个数称为点v的度 记作d v 如图8 4中d v1 3 d v2 4 d v3 4 d v4 3 度为零的点称为弧立点 度为1的点称为悬挂点 悬挂点的边称为悬挂边 度为奇数的点称为奇点 度为偶数的点称为偶点 端点的度d v 点v作为端点的边的个数奇点 d v 奇数 偶点 d v 偶数 悬挂点 d v 1 悬挂边 与悬挂点连接的边 孤立点 d v 0 空图 E 无边图 V v1 v2 v3 v4 v5 v6 v7 d v1 3 d v2 5 d v3 4 d v4 4 d v5 1 d v6 3 d v7 0 其中v5为悬挂点 v7为孤立点 定理8 1所有顶点度数之和等于所有边数的2倍 证明 因为在计算各个点的度时 每条边被它的两个端点个用了一次 定理8 2在任一图中 奇点的个数必为偶数 证明 设V1 V2分别是图G中奇点和偶点的集合 由定理8 1 有 因为是偶数 也是偶数 因此 也必是偶数 从而V1中的点数是偶数 二 图的连通性链 由两两相邻的点及其相关联的边构成的点边序列 如 v0 e1 v1 e2 v2 e3 v3 vn 1 en vn v0 vn分别为链的起点和终点 记作 v0 v1 v2 v3 vn 1 vn 简单链 链中所含的边均不相同 初等链 链中所含的点均不相同 也称通路 圈 若v0 vn则称该链为开链 否则称为闭链或回路或圈 简单圈 如果在一个圈中所含的边均不相同初等圈 除起点和终点外链中所含的点均不相同的圈 连通图 图中任意两点之间均至少有一条通路 否则称为不连通图 初等链 v1 v2 v3 v6 v7 v5 初等圈 v1 v2 v3 v5 v4 v1 简单圈 v4 v1 v2 v3 v5 v7 v6 v3 v4 简单链 v1 v2 v3 v4 v5 v3 以后除特别声明 均指初等链和初等圈 连通图 子图定义 如果V2 V1 E2 E1称G2是G1的子图 真子图 如果V2 V1 E2 E1称G2是G1的真子图 部分图 如果V2 V1 E2 E1称G2是G1的部分图或支撑子图 导出子图 如果V2 V1 E2 vi vj vi vj V2 称G2是G1中由V2导出的导出子图 设G1 V1 E1 G2 V2 E2 G1 G2真子图 G3子图部分图 G4导出子图 G5生成树 G6G5余树 有向图 关联边有方向弧 有向图的边a u v 起点u 终点v 路 若有从u到v不考虑方向的链 且各方向一致 则称之为从u到v的路 初等路 各顶点都不相同的路 初等回路 u v的初等路 连通图 若不考虑方向是无向连通图 强连通图 任两点有路 三 图的矩阵表示 图的图形表示法在较为简单的情况下由于比较直观 所以有一定的优越性 但对于比较复杂的图这种表示方法就不太方便了 故目前一般多用矩阵方法表示图 由于这种方法表示简单 使用方便 目前应用较为普遍 更重要的是 它把图的问题变成为数学计算问题 因而对图的研究可借助于计算机来实现 图的矩阵表示法有权矩阵 邻接矩阵 关联矩阵 回路矩阵等 这里仅介绍其中的两种 定义 对于网络 赋权图 G V E 其中边有权 构造矩阵 其中 称矩阵A为网络G的权矩阵 定义设图G V E 中顶点的个数为n 构造一个矩阵 其中 称矩阵A为网络G的邻接矩阵 例如图所示 其权矩阵为 邻接矩阵为 因为G是无向图 所以邻接矩阵是对称的 8 2树和最小支撑树 一 树的概念和性质在各种各样的图中 有一类图是十分简单又非常具有应用价值的图 这就是树 例8 3已知有六个城市 它们之间要架设电话线 要求任意两个城市均可以互相通话 并且电话线的总长度最短 回本章目录 如果用六个点v1 v6代表这六个城市 在任意两个城市之间架设电话线 即在相应的两个点之间连一条边 这样 六个城市的一个电话网就作成一个图 表示任意两个城市之间均可以通话 这个图必须是连通图 并且 这个图必须是无圈的 否则 从圈上任意去掉一条边 剩下的图仍然是六个城市的一个电话网 图8 8是一个不含圈的连通图 代表了一个电话线网 图8 8 v6 v3 v4 v2 v5 v1 定义8 1一个无圈的连通图叫做树 下面介绍树的一些重要性质 定理8 3设图G V E 是一个树 P G 2 P G 为无向图点数 图G中至少有两个悬挂点 定理8 4图G V E 是一个树的充要条件是G不含圈 并且有且仅有P 1条边 定理8 5图G V E 是一个树的充要条件是G是连通图 并且有且仅有p 1条边 定理8 6图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链 从以上定理 不难得出以下结论 1 从一个树中任意去掉一条边 那么剩下的图不是连通图 亦即 在点集合相同的图中 树是含边数最少的连通图 2 在树中不相邻的两个点之间加上一条边 那么恰好得到一个圈 二 支撑树 定义8 2设图K V EI 是图G V E 的 一支撑子图 如果图K V EI 是一个树 那么称K是G的一个支撑树 例如 图8 10b是图8 10a的一个支撑树 图8 10 显然 如果图K V EI 是图G V E 的一个支撑树 那么K的边数是p G 1 G中不属于支撑树K的边数是q G p G 1 定理8 7一个图G有支撑树的充要条件是G是连通图 证明 充分性 设图G是连通的 若G不含圈 则按照定义 G是一个树 从而G是自身的一个支撑树 若G含圈 则任取G的 一个圈 从该圈中任意去掉一条边 得到图G的一支撑子图G1 若G1不含圈 则G1是G的一个支撑树 若G1仍然含圈 则任取G1的一个圈 再从圈中任意去掉一条边 得到图G的一支撑子图G2 依此类推 可以得到图G的一个支撑子图GK 且不含圈 从而GK是一个支撑树 定理8 7充分性的证明 提供了一个寻找连通图支撑树的方法叫做 破圈法 就是从图中任取一个圈 去掉一条边 再对剩下的图重复以上步骤 直到不含圈时为止 这样就得到一个支撑树 例8 4用破圈法求出图8 11的一个支撑树 图8 11 取一个圈 v1 v2 v3 v1 在一个圈中去掉边e3 在剩下的图中 再取一个圈 v1 v2 v4 v3 v1 去掉边e4 再从圈 v3 v4v5 v3 中去掉边e6 再从圈 v1 v2 v5 v4 v3 v1 中去掉边e7 这样 剩下的图不含圈 于是得到一个支撑树 如图8 12所示 图8 12 三 最小支撑树问题定义8 3如果图G V E 对于G中的每一条边 vi vj 相应地有一个数Wij 那么称这样的图G为赋权图 Wij称为边 vi vj 的权 这里所指的权 是具有广义的数量值 根据实际研究问题的不同 可以具有不同的含义 例如长度 费用 流量等等 赋权图在图论及实际应用方面有着重要的地位 被广泛应用于现代科学管理和工程技术等领域 最小支撑树问题就是赋权图的最优化问题之一 设G V E 是一个连通图 G的每一条 vi vj 对应一个非负的权Wij 定义8 4如果图T V EI 是图G的一个支撑树 那么称EI上所有边的权的和为支撑树T的权 记作S T 如果图G的支撑树T 的权S T 在G的所有支撑树T中的权最小 即S T minTS T 那么称T 是G的最小支撑树 如前所述 在已知的几个城市之间联结电话线网 要求总长度最短和总建设费用最少 一个问题的解决可以归结为最小支撑树问题 再如 城市间交通线的建造等 都可以归结为这一类问题 下面介绍寻求最小支撑树的方法 破圈法 在给定的连通图中任取一个圈 去掉权最大的一条边 如果有两条以上权最大的边 则任意 去掉一条 在剩下的图中 重复以上步骤 直到得到一个不含圈的连通图为止 这个图便是最小支撑树 例8 5某六个城市之间的道路网如图8 13a所示 要求沿着已知长度的道路联结六个城市的电话线网 使得电话线的总长度最短 图8 13a 图8 13b 解 这个问题的解决就是要求所示赋权图8 13a中的最小支撑树 用破圈法求解 任取一个圈 例如 v1 v2 v3 v1 去掉这个圈中权最大的边 v1 v3 再取一个圈 v3 v5 v2 v3 去掉边 v2 v5 再取一个圈 v3 v5 v4 v2 v3 去掉边 v3 v5 再取一个圈 v5 v6 v4 v5 这个圈中 有两条权最大的边 v5 v6 和 v4 v6 任意去掉其中的一条 例如 v5 v6 这时得到一个 不含圈的图 如图8 13b所示 即是最小支撑树 关于破圈法正确性的证明略去 例用破圈法求出下图中的最小支撑树 破圈法和生长法两个方法 1 在网络图中寻找一个圈 若不存在圈 则已经得到最小支短树或网络不存在最小支撑树 2 去掉该圈中权数最大的边 反复重复 两步 直到最小支撑树 1 破圈法 从网络图中任意节点开始寻找与该节点关联的权数最小的边 得到另一节点后 再从这个新节点开始寻找与该节点关联的权数最小的另一边 注意寻找过程中 节点不得重复 即在找最小权数边时不考虑已选过的边 反复进行 直到得到最小支撑树或证明网络不存在最小支撑树 2 成长法 避圈法 例用成长法求出下图中的最小支撑树 最短树 一 引言最短路径问题是图论中十分重要的最优化问题之一 它作为一个经常被用到的基本工具 可以解决生产实际中的许多问题 比如城市中的管道铺设 线路安排 工厂布局 设备更新等等 也可以用于解决其它的最优化问题 8 3最短路问题 回本章目录 例8 6如图8 14所示的单行线交通网 每个弧旁边的数字表示这条单行线的长度 现在有一个人要从v1出发 经过这个交通网到达v8 要寻求是总路程最短的线路 图8 14 1 从v1到v8的路线是很多的 比如从v1出发 经过v2 v5到达v8或者从v1出发 经过v4 v6 v7到达v8等等 但不同的路线 经过的总长度是不同的 例如 按照第一个线路 总长度是6 1 6 13单位 按照第二个路线 总长度是1 10 2 4 17单位 从这个例子中 可以给出一般意义下的最短路问题 设一个赋权有向图D V A 对于每一个弧a vi vj 相应地有一个权wij vs vt是D中的两个顶点 P是D中从vs到vt的任意一条路 定义路的权是P中所有弧的权的和 记作S p 最短路问题就是要在所有从vs到vt的路P中 寻找一个权最小的路P0 亦即S P0 minS p P0叫做从vs到vt的最短路 P0的权S P0 叫做从vs到vt的距离 记作d vs vt 由于D是有向图 很明显d vs vt 与d vt vs 一般不相等 求解最短路的方法很多 该问题完全可以看成一个网络问题 可以利用后面的最小费用流算法可以求解 也可以用前面介绍的动态规划方法求解 但计算效率最高的还是图论的方法 下面介绍几种算法 二 狄克斯屈拉 Dijkstra 算法下面介绍在一个赋权有向图中寻求最短路的方法 Dijkstra算法 它是在1959年提出来的 目前公认 在所有的权wij 0时 这个算法是寻求最短路问题最好的算法 并且 这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路 Dijkstra算法的基本思想是从vs出发 逐步向外寻找最短路 在运算过程中 与每个点对应 记录一个数 叫做一个点的标号 它或者表示从vs到该点的最短路权 叫做P标号 permanetlabel 或者表示从vs到该点最短路权的上界 叫做T标号 tentativelabel 算法的每一步是去修改T标号 把某一个具有T标号的点改变为具有P标号的点 使图D中具有P标号的顶点多一个 这样 至多经过n 1步 就可求出从vs到各点vj及终点vt最短路 算法步骤 给始点vs以P标号 这表示从vs到vs的最短距离为0 其余节点均给T标号 2 设节点vi为刚得到P标号的点 考虑点vj 其中 且vj为T标号 对vj的T标号进行如下修改 3 比较所有具有T标号的节点 把最小者改为P标号 即 当存在两个以上最小者时 可同时改为P标号 若全部节点均为P标号 则停止 否则用vk代替vi 返回步骤 2 例一 用Dijkstra算法求下图从v1到v6的最短路 解 1 首先给v1以P标号 给其余所有点T标号 2 3 4 5 6 7 8 9 10 反向追踪得v1到v6的最短路为 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求从1到8的最短路径 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 w1 0 min c12 c14 c16 min 0 2 0 1 0 3 min 2 1 3 1X 1 4 p4 1 p4 1 p1 0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 4 min c12 c16 c42 c47 min 0 2 0 3 1 10 1 2 min 2 3 11 3 2X 1 2 4 p2 2 p1 0 p4 1 p2 2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 min c13 c23 c25 c47 min 0 3 2 6 2 5 1 2 min 3 8 7 3 3X 1 2 4 6 p6 3 p2 2 p4 1 p1 0 p6 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 min c23 c25 c47 c67 min 2 6 2 5 1 2 3 4 min 8 7 3 7 3X 1 2 4 6 7 p7 3 p2 2 p4 1 p1 0 p6 3 p7 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min c23 c25 c75 c78 min 2 6 2 5 3 3 3 8 min 8 7 6 11 6X 1 2 4 5 6 7 p5 6 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min c23 c53 c58 c78 min 2 6 6 9 6 4 3 8 min 8 15 10 11 8X 1 2 3 4 5 6 7 p3 8 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 min c38 c58 c78 min 8 6 6 4 3 7 min 14 10 11 10X 1 2 3 4 5 6 7 8 p8 10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 8 1到8的最短路径为 1 4 7 5 8 长度为10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 求从V1到V8的最短路线 由此看到 此方法不仅求出了从V1到V8的最短路长 同时也求出了从V1到任意一点的最短路长 将从V1到任一点的最短路权标在图上 即可求出从V1到任一点的最短路线 本例中V1到V8的最短路线是 v1 v2 v5 v6 v8 例8 6 三 逐次逼近法 前面已经说过 Dijkstra算法只能计算非负权的情况 本算法可用于网络中带有负权的边时 求某指定点到网络中任意点的最短距离 算法的基本思路与步骤 首先设任一点vi到任一点vj都有一条弧 如果在图G中 则添加弧 并令 显然 从v1到vj的最短路是从v1出发 沿着这条路到某个点vi再沿弧 vi vj 到vj 则v1到vi的这条路必然也是v1到vi的所有路中的最短路 设P1j表示从v1到vj的最短路长 P1i表示从v1到vi的最短路长 则有下列方程 利用如下的递推公式 开始时 令即用v1到vj的直接距离做初始解 从第二步起 使用递推公式 求 当进行到第t步 若出现则停止计算 即为v1到各点的最短路长 例二 求图中v1到各点的最短路 可以看出 当t 4时 有 因此 表中的最后一列 就是从v1到v1 v2 v8的最短路权 表中没有数字的空格表示 为了求出从v1到各个点的最短路 一般采用反向追踪的方法 如果已知P1j 那么寻求一个点vk 使得P1k Lkj P1j 然后记录下 vk vj 再看P1k 寻求一个点vi 使得P1i Lik P1k 依次类推 一直到达v1为止 这样 从v1到vj的最短路是 v1 vi vk vj 在本例中 由表可知 P18 6 由于P16 L68 1 7 记录下v6 由于P13 L36 P16 记录下v3 由于P11 L13 P13 于是 从v1到v8的最短路是 v1 v3 v6 v8 对于递推公式中的的实际意义为 从v1到vj点 最多含有K 1中间点的最短路权 所以在含有n个点的图中 如果不含有总权小于零的回路 求从v1到任一点的最短路权 用上述算法最多经过n 1次迭代必定收敛 如果图中含有总权小于零的回路 则可能某些最短路权没有下界 0 0 v3 5 v1 2 v3 7 v2 3 v4 5 v3 1 v6 6 例三 求 5年内 哪些年初购置新设备 使5年内的总费用最小 解 1 分析 可行的购置方案 更新计划 是很多的 如 1 每年购置一台新的 则对应的费用为 11 11 12 12 13 5 5 5 5 5 842 第一年购置新的 一直用到第五年年底 则总费用为 11 5 6 8 11 18 59显然不同的方案对应不同的费用 2 方法 将此问题用一个赋权有向图来描述 然后求这个赋权有向图的最短路 求解步骤 1 画赋权有向图 设Vi表示第i年初 Vi Vj 表示第i年初购买新设备用到第j年初 j 1年底 而Wij表示相应费用 则5年的一个更新计划相当于从V1到V6的一条路 2 求解 标号法 W12 11 5 16W13 11 5 6 22W14 11 5 6 8 30W15 11 5 6 8 11 41W16 11 5 6 8 11 18 59 W23 11 5 16W24 11 5 6 22W25 11 5 6 8 30W26 11 5 6 8 11 41 W45 12 5 17W46 12 5 6 23W56 13 5 18 W34 12 5 17W35 12 5 6 23W36 12 5 6 8 31 例四 某工厂使用一种设备 这种设备在一定的年限内随着时间的推移逐渐损坏 所以工厂在每年年初都要决定设备是否更新 若购置设备 每年需支付购置费用 若继续使用旧设备 需要支付维修与运行费用 而且随着设备的老化会逐年增加 计划期 五年 内中每年的购置费 维修费与运行费如表所示 工厂要制定今后五年设备更新计划 问采用何种方案才能使包括购置费 维修费与运行费在内的总费用最小 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 8 4最大流问题 在许多实际的网络系统中都存在着流量和最大流问题 例如铁路运输系统中的车辆流 城市给排水系统的水流问题等等 而网络系统最大流问题是图与网络流理论中十分重要的最优化问题 它对于解决生产实际问题起着十分重要的作用 回本章目录 图8 19是联结某个起始地vs和目的地vt的交通运输网 每一条弧vi旁边的权cij表示这段运输线的最大通过能力 货物经过交通岗从vs运送到vt 要求指定一个运输方案 使得从vs到vt的货运量最大 这个问题就是寻求网络系统的最大流问题 问题描述连通网络G V A 有m个节点 n条弧 弧eij上的流量上界为cij 求从起始节点vs到终点vt的最大流量 图8 19 二基本概念定义8 5设一个赋权有向图D V A 在V中指定一个发点vs和一个收点vt 其它的点叫做中间点 对于D中的每一个弧 vi vj A 都有一个权叫做弧的容量 我们把这样的图D叫做一个网络系统 简称网络 记做D V A C 网络D上的流 是指定义在弧集合A上的一个函数f f vi vj fij f vi vj fij叫做弧 vi vj 上的流量 例如图8 19就是一个网络 每一个弧旁边的权就是对应的容量 最大通过能力 cij 图8 20表示的就是这个网络上的一个流 运输方案 每一个弧上的流量fij就是运输量 例如fs1 5 fs2 3 f13 2等等 对于实际的网络系统上的流 有几个显著的特点 1 发点的总流出量和收点的总流入量必相等 2 每一个中间点的流入量与流出量的代数和等于零 3 每一个弧上的流量 不能超过它的最大通过能力 即容量 于是有 图8 20 定义8 6网络上的一个流f叫做可行流 如果f满足以下条件 1 容量条件 对于每一个弧 vi vj A 有0 fij cij 2 平衡条件 对于发点vs 有 对于收点vt 有 对于中间点 有 任意一个网络上的可行流总是存在的 例如零流v f 0 就是满足以上条件的可行流 网络系统中最大流问题就是在给定的网络上寻求一个可行流f 其流量v f 达到最大值 设流f fij 是网络D上的一个可行流 我们把D中fij cij的弧叫做饱和弧 fij cij的弧叫 其中发点的总流量 或收点的总流量 v f 叫做这个可行流的流量 做非饱和弧 fij 0的弧为非零流弧 fij 0的弧叫做零流弧 在图8 20中 v4 v3 是饱和弧 其他的弧是非饱和弧 并且都是非零流弧 设 是网络D中连接发点 s和收点vt的一条链 定义链的方向是从 s到vt 于是链 上的弧被分为两类 一类是弧的方向与链的方向相同 叫做前向弧 前向弧的集合记做 二类是弧的方向与链的方向相反 叫做后向弧 后向弧的集合记做 例如在图8 19中 在链 vs v1 v2 v3 v4 vt 中 vs v1 v1 v2 v2 v3 v4 vt v4 v3 增广链 如果链 满足以下条件 1 在弧 vi vj 上 有0 fij cij 即 中的每一条弧是非饱和弧 2 在弧 vi vj 上 有0 fij cij 即 中的每一条弧是非零流弧 例如在图8 20中 链 vs v1 v2 v3 v4 vt 就是一条增广链 定义8 8设一个网络D V A C 如果点集V被分为两个非空集合v1和 发点vs v1 收点vt 那么将弧集 v1 叫做是分离vs和vt的截集 如右图 取 截集截集容量由于V的分解方法不同 所以截集就不相同 对应的截集的容量也不相同 其中容量最小的称为最小截集 定义8 9设一个截集 V1 将截集 V1 中所有的弧的容量的和叫做截集的容量 记做s V1 亦即 下面的事实是显然的 一个网络D中 任何一个可行流f的流量v f 都小于或等于这个网络中任何一个截集 V1 的容量 并且 如果 网络上的一个可行流f 和网络中的一个截集 V1 满足条件v f c V1 那么f 一定是D上的最大流 而 V1 一定是D的所有的截集中容量最小的一个 即最小截集 定理8 8网络中的一个可行流f 是最大流的充分必要条件是 不存在关于f 的增广链 定理8 9在一个网络D中 最大流的流量等于分离vs和vt的最小截集的容量 定理8 8为我们提供了一个寻求网络系统最大流的方法 亦即 如果网络D中有一个可行流f 只要判断网络是否存在关于可行流f的增广链 如果没有增广链 那么f一定是最大流 如有增广链 那么可以按照定理8 9中必要性 不断改进和增大可行流f的流量 最终可以得到网络中的一个最大流 三 标号法从网络中的一个可行流f出发 如果D中没有f 可以令f是零流 运用标号法 经过标号过程和调整过程 可以得到网络中的一个最大流 下面用给顶点标号的方法来定义V1 在标号过程中 有标号的顶点是V1 中的点 没有标号的点不是V1 中的点 如果vt有了标号 表示存在一条关于f的增广链 如果标号过程无法进行下去 并且vt未被标号 则表示不存在关于f的增广链 这样 就得到了网络中的一个最大流和最小截集 1 标号过程标号过程开始 先给vs标号 0 取一个已标号的点vi 对于vi一切未标号的邻接点vj按下列规则处理 1 如果在弧 vi vj 上 fij cij 那么给vj标号 vi l vj 其中l vj min l vi cij fij 2 如果在弧 vj vi 上 fji 0 那么给vj标号 vi l vj 其中l vj min l vi fji 重复以上步骤 直到vt被标号或标号过程无法进行下去 则标号法结束 这时的可行流就是最大流 2 调整过程设 是一条从vs到vt的可增广链 的前向边和后向边分别用 和 表示 取调整量 l vt 即 为vt的第二个标号 但是 如果vt被标上号 表示得到一条增广链 转入下一步调整过程 其它不变 令再去掉所有的标号 对新的可行流f f ij 重新进行标号过程 直到找到网络D的最大流为止 例8 8求图8 21的网络最大流 弧旁的权数表示 cij fij 图8 20例8 8网络图 解 用标号法 1 标号过程 1 首先给vs标号 0 2 看vs 在弧 vs v2 上 fs2 cs3 3 不具备标号条件 在弧 vs v1 上 fs1 10 故给v2标号 v1 l v2 其中l v2 min l v1 f21 min 4 1 1 图8 21例8 8网络图 0 vs 4 v1 1 v2 1 v2 1 v3 1 4 看v2 在弧 v2 v4 上 f24 30 故给v3标号 v2 l v3 其中l l v3 min l v2 f32 min 1 1 1 5 在v3 v4中任意选一个 比如v3 在弧 v3 vt 上 f3t 1 c3t 2 故给vt标号 v3 l vt 其中l vt min l v3 c3t f3t min 1 1 1 因为vt被标上号 根据标号法 转入调整过程 2 调整过程从vt开始 按照标号点的第一个标号 用反向追踪的方法 找出一条从vs到vt的增广链 如图8 22中双箭线所示 不难看出 vs v1 v3 vt v2 v1 v3 v2 取 1 在 上调整f 得到 图8 22例8 8网络图 5 2 1 0 1 0 2 2 cij fij 调整后的可行流f 如图8 22所示 再对这个可行流从新进行标号过程 寻找增广链 首先给vs标号 0 看vs 给v1标号 vs 3 看v1 在弧 v1 v3 上 f13 c13 弧 v2 v1 上 f21 0 均不符合条件 因此标号过程无法进行下去 不存在从vS到vt的增广链 算法结束 这时 网络中的可行流f 即是最大流 最大流的流量v f fs1 fs2 5 同时 也找出D的最小截集 V1 其中V1是标号的集合 是未标号的集合 0 vs 3 图8 23例8 8网络图 例8 9求图8 24所示网络的最大流 图8 24例8 9网络图 解 给定初始可行流为全零流 即f 0 0 给vs标号 0 检查vs 给v1标号 vs 4 给v2标号 vs 3 给v3标号 vs 10 0 vs 4 vs 3 vs 10 检查v1 给v4标号 v1 1 检查完毕 v1 1 检查v2 给v5标号 v2 3 检查完毕 v2 3 检查v5 给vt标号 v5 3 检查完毕 v5 3 因为终点vt已标号 故找出一条从vs到vt的增广链 vs v2 v5 vt 取 3 vs 4 v1 3 vs 10 v1 1 v2 2 0 v5 2 vs 2 v3 3 vs 10 v2 3 v3 4 0 v4 3 0 vs 2 vs 10 v3 4 v5 2 v5 3 0 vs 2 vs 4 v1 1 v1 1 v4 1 0 vs 4 vs 1 v3 1 v5 1 v4 1 0 vs 1 vs 3 v1 1 v2 1 v4 1 0 vs 3 首先给vs标号 0 看vs 给v3标号 vs 3 看v3 在弧 v3 v2 上 f32 c32 弧 v3 v5 上 f35 c35 均不符合条件 因此标号过程无法进行下去 不存在从vS到vt的增广链 算法结束 最大流量f 14 8 5最小费用最大流问题 在实际的网络系统中 当涉及到有关流的问题的时候 我们往往不仅仅考虑的是流量 还经常要考虑费用的问题 比如一个铁路系统的运输网络流 即要考虑网络流的货运量最大 又要考虑总费用最小 最小费用最大流问题就是要解决这一类问题 回本章目录 我们首先考察 在一个网络D中 当沿可行流f的一条增广链 以调整量 1改进f 得到的新可行流f 的流量 有v f 设一个网络D V A C 对于每一个弧 vi vj A 给定一个单位流量的费用bij 0 网络系统的最小费用最大流问题 是指要寻求一个最大流f 并且流的总费用达到最小 v f 1 而此时总费用b f 比b f 增加了 结论 如果可行流f在流量为v f 的所有可行流中的费用最小 并且 是关于f的所有增广链中的费用最小的增广链 那么沿增广链 我们将叫做这条增广链的费用 调整可行流f 得到的新可行流f 也是流量为v f 的所有可行流中的最小费用流 依次类推 当f 是最大流时 就是所要求的最小费用最大流 显然 零流f 0 是流量为0的最小费用流 一般地 寻求最小费用流 总可以从零流f 0 开始 下面的问题是 如果已知f是流量为v f 的最小费用流 那么就要去寻找关于f的最小费用增广链 对此 重新构造一个赋权有向图M f 其顶点是原网络D的顶点 而将D中的每一条弧 vi vj 变成两个相反方向的弧 vi vj 和 vj vi 并且定义M f 中弧的权wij为 并且将权为 的弧从M f 中略去 这样 在网络D中寻找关于f的最小费用增广链就等于价于在M f 中寻求从vs到vt的最短路 算法开始 取零流f 0 0 一般地 如果在第K 1步得到最小费用流f K 1 则构造图M f k 1 在图M f k 1 中 寻求从vs到vt的最短路 如果存在最短路 则f k 1 就是最小费用最大流 如果存在最短路 则在原网络D中得到相对应 一一对应 的增广链 0 在增广链 上对f k 1 进行调整 取调整量 令 得到一个新的可行流f k 在对f k 重复以上的步骤 直到D中找不到相对应的增广链时为止 例8 9求图8 24所示网络中的最小费用最大流 弧旁的权是 bij cij 图8 24 解 1 取初始可行流为零流f 0 0 构造赋权有向图M f 0 求出从vs到vt的最短路 vs v2 v1 vt 如图8 25a中双箭头所示 图8 25a 2 在原网络D中 与这条最短路相对应的增广链为 vs v2 v1 vt 3 在 上对f 0 0 进行调整 取 5 得到新可行流f 1 如图8 25b所示 按照以上的算法 依次类推 可以得到f 1 f 2 f 3 f 4 流量分别为5 7 10