图与网络模型及方法ppt课件.ppt

图与网络模型及方法 图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集 图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图 绪论 图论起源于18世纪 第一篇图论论文是瑞士数学家欧拉于1736年发表的 哥尼斯堡的七座桥 1847年 克希霍夫为了给出电网络方程而引进了 树 的概念 1857年 凯莱在计数烷n2n 2CH的同分异构物时 也发现了 树 哈密尔顿于1859年提出 周游世界 游戏 用图论的术语 就是如何找出一个连通图中的生成圈 绪论 近几十年来 由于计算机技术和科学的飞速发展 大大地促进了图论研究和应用 图论的理论和方法已经渗透到物理 化学 通讯科学 建筑学 运筹学 生物遗传学 心理学 经济学 社会学等学科中 绪论 图论中所谓的 图 是指某类具体事物和这些事物之间的联系 如果我们用点表示这些具体事物 用连接两点的线段 直的或曲的 表示两个事物的特定的联系 就得到了描述这个 图 的几何形象 图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型 借助于图论的概念 理论和方法 可以对该模型求解 哥尼斯堡七桥问题 这个图是连通的 且每个点都与偶数线相关联 绪论 图与网络是运筹学 OperationsResearch 中的一个经典和重要的分支 所研究的问题涉及经济管理 工业工程 交通运输 计算机科学与信息技术 通讯与网络技术等诸多领域的最短路问题 最大流问题 最小费用流问题和匹配问题等都是图与网络的基本问题 图 由若干个点和连接这些点的连线所组成的图形 vi 图中的点 称为顶点 代表具体事物 研究对象 ei 图中的连线 称为边 对象之间的联系 m G E G的边数 简记为m n G V G的顶点数 简记为n 一 图的概念 记V vi 点的集合 E ei 边的集合 G V E G 一个图 m 6 n 5 图的基本概念 有向图 无向图 边e vi vj 有方向vi为始点 vj为终点 边e vi vj 无方向 此时 vi vj vj vi e4 v3 v4 v4 v3 e4 v3 v4 v4 v3 e5 v3 v4 v4 v3 此时 vi vj vj vi e5 v4 v3 v3 v4 图 有向图 无向图 二 常用名词 1 端点和关联边 2 相邻点和相邻边 3 多重边与环 4 多重图和简单图 无环也无多重边的图称为简单图 含有多重边的图称为多重图 5 次 6 悬挂点和悬挂边 次为1的点称为悬挂点 与悬挂点相联的边称为悬挂边 7 孤立点 8 奇点与偶点 G的边数m 6 性质1 在图G V E 中 所有点的次之和是边数m的两倍 证明 由于每条边均与两个顶点关联 因此在计算顶点的次时每条边都计算了两遍 所以顶点次数的总和等于边数的二倍 三 次 度 的性质 性质2 在任何图G V E 中 奇点的个数为偶数 证明 设V1 V2分别是图G中奇点和偶点的集合 则V1 V2 V V1 V2 有性质1 因为V2是偶点的集合 d vi i V2 均为偶数 所以 只有偶数个奇数相加才能得到偶数 所以V1中的点 即奇点的个数为偶数 四 链 路 连通图 1 链 对于无向图G V E 若图G中有一个点与边的交替序列 vi0 ei1 vi1 ei2 vik 1 eik vik 且eit vit 1 vit t 1 2 k 则称该交替序列 为连结vi0和vik的一条链 简单链 中只有重复的点而无重复边者为简单链 初等链 中没有重复的点和重复边者为初等链 圈 无向图G中 连结vi0与vik的一条链 当vi0与vik是同一个点时 称此链为圈 圈中只有重复点而无重复边者为简单圈 既 除起点 终点重复外 无重复点也无重复边者为初等圈 不是链 初等链 简单链 简单圈 初等圈 2路 在有向图D V A 中 若有从vi0到vik不考虑方向的链 且各边方向一致 则称之为从vi0到vik的一条路 对于有向图可以类似于无向图定义链和圈 初等链 圈 简单链 圈 此时不考虑边的方向 而当链 圈 上的边方向相同时 称为道路 回路 对于无向图来说 道路与链 回路与圈意义相同 3连通图 一个图中任意两点间至少有一条链 或路 相连的图 连通图 非连通图 五 网络在实际问题中 往往只用图来描述所研究对象之间的关系还不够 与图联系在 起的 通常还有与点或边有关的某些数量指标 通常称之为 权 权可以代表如距离 费用 通过能力 容量 等等 这种带有某种数量指标的图称为网络 赋权图 如公路交通图 vi表示城市 ei表示公路w ei 表示公路ei的长度 如w e2 50表示城市v2与城市v3之间的距离是50千米 六 完全图 偶图 1 完全图 一个简单图 若任意两个顶点之间均有一条边相连 则称这样的图为完全图 对于完全图 由于每个顶点与所有其余顶点都有一条边相连 所以在有n个顶点的完全图中 各个顶点的次均为 n 1 2 偶图 若图G的顶点能分成两个互不相交的非空集合V1和V2 使在同一集合中的任意两个顶点均不相邻 称这样的图为偶图 也称为二部图 若偶图的顶点集合V1 V2之间的每一对不同顶点都有一条边相连 称这样的图为完全偶图 v2 v3 v4 v5 v2 v3 v4 v5 v1 v1 完全图 完全 偶图 定理一个图为偶图的充分必要条件该图无奇圈 七 子图 部分图对于图G1 V1 E1 和图G2 V2 E2 若有 称G1是G2的一个子图 若有 称G1是G2的一个部分图 生成子图 部分图也是子图 但子图不一定是部分图 生成子图 七 子图 部分图 部分图也是子图 但子图不一定是部分图 生成子图 对于图G1 V1 E1 和图G2 V2 E2 若有 称G1是G2的一个子图 若有 称G1是G2的一个部分图 生成子图 八 前向弧与后向弧设 是一条从vs到vt的链 则链 上与链的方向一致的弧称为前向弧 记这些弧为 链 上与链的方向相反的弧称为后向弧 记这些弧为 vs v1 v2 v3 v4 v5 vt 前向弧与后向弧 子图设G1 V1 E1 G2 V2 E2 子图定义 如果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导出的导出子图 九 图的矩阵表示用矩阵表示图对研究图的性质及应用常常是比较方便的 定义 网络 赋权图 G V E 其边 vi vj 有权 ij 构造矩阵A aij n n 其中 称矩阵A为网络G的权矩阵 例 写出下图的权矩阵 v1 v2 v3 v4 v5 7 6 5 4 2 4 9 3 8 定义 对于图G V E V n 构造一个矩阵A aij n n 其中 称矩阵A为图G的邻接矩阵 例 写出下图的邻接矩阵 v1 v3 v5 v2 v4 v6 当G为无向图时 邻接矩阵为对称矩阵 最短轨道问题 给出了一个连接若干个城镇的铁路网络 在这个网络的两个指定城镇间 找一条最短铁路线 以各城镇为图G的顶点 两城镇间的直通铁路为图G相应两顶点间的边 得图G 对G的每一边e 赋以一个实数w e 直通铁路的长度 称为e的权 得到赋权图G G的子图的权是指子图的各边的权和 问题就是求赋权图G中指定的两个顶点u0 v0间的具最小权的轨 这条轨叫做u0 v0间的最短路 它的权叫做u0 v0间的距离 亦记作d u0 v0 最短轨道问题求法 Dijkstra算法 基本思想是按距u0从近到远为顺序 依次求得u0到G的各顶点的最短路和距离 直至v0 或直至G的所有顶点 算法结束 为避免重复并保留每一步的计算信息 采用了标号算法 最短轨道问题求法 Dijkstra算法 定义 连通且不含圈的无向图称为树 记作T V E 二 树 树可以有很多等价的定义 以下定理中的各命题都体现树的特征 定理设G V E 是一无向图 V n E m 则以下命题是等价的 1 G是树 2 G的每对顶点之间有唯一的一条路 3 G连通且m n 1 4 G无圈且m n 1 5 G无圈 在G的任一对顶点上加一新边后产生圈 6 G连通 但删去任何一边后不再连通 定理 无向图G有生成树当且仅当G连通 证明 必要性显然 只证充分性 若G无圈 则G本身就是G的生成树 若G有圈C 则在G中删去C的一条边 所得的图是连通的 继续这个过程 直到所得的图T无圈为止 则T就是G的一棵生成树 定义 若图G的生成子图是一棵树 则称该树为G的生成树 支撑树 或简称为图G的树 b 为 a 图的生成树 最小生成树的求法 避圈法与破圈法 定义 树的各条边称为树枝 一般图G的生成树有多个 称其中树枝总长度最小的生成树为最小树 避圈法 在图G中 每步选出一条边e 使它与已选边不构成圈 且e是未选边中长度最小的边 直到选够n 1边为止 v1 v2 v3 v8 v7 v6 v5 v4 v0 4 1 1 2 1 3 1 4 4 4 5 2 3 5 5 2 v1 v2 v3 v8 v7 v6 v5 v4 v0 1 1 2 1 1 2 3 2 v1 v2 v3 v8 v7 v6 v5 v4 v0 4 1 1 2 1 3 1 4 4 4 5 2 3 5 5 2 v1 v2 v3 v8 v7 v6 v5 v4 v0 1 1 2 1 1 2 3 2 破圈法 从网络图N中任取一回路 去掉该回路中权数最大的一条边 得一子网络图N1 在N1中再任取一回路 去掉该回路中权数最大的一条边 得一子网络图N2 如此继续下去 直到剩下的子图中不再含回路为止 该子图就是N的最小生成树 v1 v2 v3 v8 v7 v6 v5 v4 v0 4 1 1 2 1 3 1 4 4 4 5 2 3 5 5 2 筑路选线问题 欲修筑连接n个城市的铁路 已知i城与j城之间的铁路造价为wij 设计一个线路图使总造价最低连线问题的数学模型是在连通赋权图上求权最小的生成树 赋权图的具最小权的生成树叫做最小生成树造最小生成树的两种常用算法 prim算法与Kruskal算法 prim算法构造最小生成树 设置两个集合P和Q 其中P用于存放G的最小生成树中的顶点 集合Q存放G的最小生成树中的边 令集合P的初值为 1P v 假设构造最小生成树时 从顶点v1出发 集合Q的初值为Q prim算法的思想是 从所有p P v V P的边中 选取具有最小权值的边pv 将顶点v加入集合P中 将边pv加入集合Q中 如此不断重复 直到P V时 最小生成树构造完毕 这时集合Q中包含了最小生成树的所有边 Kruskal算法构造最小生成树 可行遍问题 定义1 经过G的每条边的迹叫做G的Euler迹 闭的Euler迹叫做Euler回路或E回路 含Euler回路的图叫做Euler图 直观地讲 Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图 即不重复地行遍所有的边再回到出发点 定理6 i G是Euler图的充分必要条件是G连通且每顶点皆偶次 ii G是Euler图的充分必要条件是G连通且 iii G中有Euler迹的充要条件是G连通且至多有两个奇次点 定义包含G的每个顶点的轨叫做Hamilton 哈密顿 轨 闭的Hamilton轨叫做Hamilton圈或H圈 含Hamilton圈的图叫做Hamilton图 直观地讲 Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图 即不重复地行遍所有的顶点再回到出发点 Euler回路的Fleury算法 可行遍问题的应用 中国邮递员问题一位邮递员从邮局选好邮件去投递 然后返回邮局 当然他必须经过他负责投递的每条街道至少一次 为他设计一条投递路线 使得他行程最短 中国邮递员问题的数学模型 在一个赋权连通图上求一个含所有边的回路 且使此回路的权最小 若此连通赋权图是Euler图 则可用Fleury算法求Euler回路 此回路即为所求 对于非Euler图 1973年 Edmonds和Johnson给出下面的解法 多邮递员问题 邮局有k k 2 位投递员 同时投递信件 全城街道都要投递 完成任务返回邮局 如何分配投递路线 使得完成投递任务的时间最早 我们把这一问题记成kPP kPP的数学模型如下 旅行商 TSP 问题 一名推销员准备前往若干城市推销产品 然后回到他的出发地 如何为他设计一条最短的旅行路线 从驻地出发 经过每个城市恰好一次 最后返回驻地 是在一个赋权完全图中 找出一个有最小权的Hamilton圈 称这种圈为最优圈与最短路问题及连线问题相反 目前还没有求解旅行商问题的有效算法 所以希望有一个方法以获得相当好 但不一定最优 的解 改良圈算法 旅行商问题的数学表达式 对集 1957年 贝尔热 Berge 得到最大对集的充要条件 定理2M是图G中的最大对集当且仅当G中无M可增广轨 1935年 霍尔 Hall 得到下面的许配定理 定理3G为二分图 X与Y是顶点集的划分 G中存在把X中顶点皆许配的对集的充要条件是 S X 则 N S S 其中N S 是S中顶点的邻集 推论1 若G是k次 k 0 正则2分图 则G有完美对集 所谓k次正则图 即每顶点皆k度的图 由此推论得出下面的婚配定理 定理4每个姑娘都结识k k 1 位小伙子 每个小伙子都结识k位姑娘 则每位姑娘都能和她认识的一个小伙子结婚 并且每位小伙子也能和他认识的一个姑娘结婚 人员分派问题 工作人员x1 x2 xn去做n件工作y1 y2 yn 每人适合做其中一件或几件 问能否每人都有一份适合的工作 如果不能 最多几人可以有适合的工作 这个问题的数学模型是 G是二分图 顶点集划分为V G XUY X x1 xn Y y1 yn 当且仅当xi适合做工作yj时 xiyj E G 求G中的最大对集 人员分派问题匈牙利算法 1965年埃德门兹 Edmonds 提出匈牙利算法 匈牙利算法 i 从G中任意取定一个初始对集M ii 若M把X中的顶点皆许配 停止 M即完美对集 否则取X中未被M许配的一顶点u 记S u T iii 若N S T 停止 无完美对集 否则取y N S T iv 若y是被M许配的 设yz M S SU z T TU y 转 iii 否则 取可增广轨P u y 令M M E P U E P M 转 ii 最优分派问题 在人员分派问题中 工作人员适合做的各项工作当中 效益未必一致 我们需要制定一个分派方案 使公司总效益最大 这个问题的数学模型是 在人员分派问题的模型中 图G的每边加了权w xi yj 0表示xi干yj工作的效益 求加权图G上的权最大的完美对集 解决这个问题可以用库恩 曼克莱斯 Kuhn Munkres 算法 定义若映射l V G R 满足 x X y Y l x l y w x y 则称l是二分图G的可行顶点标号 令El xy xy E G l x l y w xy 称以lE为边集的G的生成子图为相等子图 记作Gl 可行顶点标号是存在的 例如 定理5Gl的完美对集即为G的权最大的完美对集 Kuhn Munkres算法 最短路问题最短路问题是网络理论中应用最广泛的问题之一 许多优化问题可以便用这个模型 如设备更新 管道铺设 线路安排 厂区布局等 最短路问题的一般提法 设G V E 为连通图 图中各边 vi vj 有权lij lij 表示vi vj间无边 vs vt为图中任意两点 求一条路 使它是从vs到vt的所有路中总权最小的路 即 最小 有些最短路问题是求网络中某指定点到其余所有点的最短路 或求网络中任意两点间的最短路 下面介绍三种算法 可分别用于求解这几种最短路问题 2 使用条件 网络中所有的弧 边 权均非负 即 1 基本思路基于以下原理 若序列 vs v1 vn 1 vn 是从vs到vn的最短路 则序列 vs v1 vn 1 必为从vs到vn 1的最短路 1 Dijkstra算法本算法由Dijkstra于1959年提出 可用于求解指定两点vs vt间的最短路 或从指定点vs到其余各点的最短路 下面给出Dijkstra算法基本步骤 采用标号法 可用两种标号 T标号与P标号 T标号为试探性标号 P为永久性标号 给vi点一个P标号时 表示从vs到点vi的最短路权 vi点的标号不再改变 给vi点一个T标号时 表示从vs到点vi的估计最短路权的上界 是一种临时标号 凡没有得到P标号的点都有T标号 算法每一步都把某一点的T标号改为P标号 当终点vt得到P标号时 全部计算结束 对于有n个顶点的图 最多经n一1步就可以得到从始点到终点的最短路 标号的意义 标号P 永久性标号 从始点到该标号点的最短路权 标号T 临时性标号 从始点到该标号点的最短路权上界 计算步骤 第二步 若vi为刚得到P标号的点 考虑这样的点vj vi vj 属于E 且vj为T标号 对vj的T标号进行如下的更改 T vj min T vj P vi lij 第三步 比较所有具有T标号的点 把最小者改为P标号 即 第一步 给始点vs标上永久性标号P vs 0 其余各点标临时性标号T vj 当存在两个以上最小者时 可同时改为P标号 若全部点均为P标号则停止 否则用代vi转回第二步 例 用Dijkstar算法求下图中v1到v7点的最短路 v1 v3 v2 v7 v5 v4 v6 1 7 1 3 4 4 4 5 2 5 7 2 1 首先给v1以P标号 P v1 0 其余所有点给T标号 T vi 图中 内的数表示P标号 内的数表示T标号 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 v6 7 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 5 2 由于边 v1 v2 v1 v3 v1 v4 属于E 且v2 v3 v4为T标号 所以修改这三个点的标号 T v2 min T v2 P v1 l12 min 0 4 4T v3 min T v3 P v1 l13 min 0 2 2T v4 min T v4 P v1 l14 min 0 5 5 7 3 比较所有T标号 T v3 最小 所以令P v3 2 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 5 7 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 4 9 7 4 v3为刚得到P标号的点 考察边 v3 v4 v3 v6 的端点v4 v6 T v4 min T v4 P v3 l34 min 5 2 2 4T v6 min T v6 P v3 l36 min 2 7 9 5 比较所有T标号 T v2 T v4 最小 所以令P v2 P v4 4 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 4 9 7 6 v2 v4为刚得到P标号的点 考察边 v2 v5 v4 v5 v4 v6 的端点v5 v6 T v5 min T v5 P v4 l45 P v2 l25 min 4 3 4 4 7T v6 min T v6 P v4 l46 min 9 4 4 8 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 8 7 7 v3 2 v6 7 比较所有T标号 T v5 所以令P v5 7 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 8 v3 2 v6 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 14 8 v3 2 v6 8 v5为刚得到P标号的点 考察边 v5 v6 v5 v7 的端点v6 v7 T v6 min T v6 P v5 l56 min 8 7 1 8T v7 min T v7 P v5 l57 min 7 7 14 7 7 9 比较所有T标号 T v6 最小 所以令P v6 8 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 14 8 v3 2 v6 10 v6为刚得到P标号的点 考察边 v6 v7 的端点v7 T v7 min T v7 P v6 l67 min 14 8 5 13 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 13 8 v3 2 v6 7 7 11 只有一个T标号T v7 令P v7 13 停止 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 13 8 v3 2 v6 7 计算结果见上图 v1到v7的最短路为 同时得到v1到其余各点的最短路 这个算法只适用于全部权为非负情况 如果某边的权为负 算法失效 上面的例题是针对无向图求最短路的问题 对有向图最短路的求法类似 下面以设备更新问题为例说明有向图最短路的计算方法 例 设备更新问题 某企业在四年内都要使用某种设备 在每年年初作出是购买新设备还是继续使用旧设备的决策 若购买新设备就要支付购置费 若继续使用旧设备 则需支付维修费用 这种设备在四年之内每年年初的价格以及使用不同时间 年 的设备的维修费用估计为 问题 制定一个四年之内的设备更新计划 使得四年之内的设备购置费和维修费用之和最小 可以用求最短路问题的方法来解决总费用最少的设备更新计划问题 符号的含义 vi 第i年年初购进一台新设备 v5表示第四年年底 弧 vi vj 表示第i年年初购进的设备一直使用到第j年年初 即第j 1年年底 弧 vi vj 的权数表示从第i年年初购进的设备一直使用到第j年年初所花费的购置费和维修费用的总和 如何制定使得总费用最少的设备更新计划问题可以转化最短路问题 此最短路问题如图所示 图中权数 ij的确定 12 10 2 12 13 10 2 4 16 14 10 2 4 7 23 15 10 2 4 7 14 37 23 11 2 13 24 11 2 4 17 25 11 2 4 7 24 34 12 2 14 35 12 2 4 18 45 13 2 15 下面用Dijkstra算法求v1到v5的最短路 给v1以P标号 P v1 0 其余各点给以T标号 T vi i 2 3 4 5 图中 内的数表示P标号 内的数表示T标号 2 由于 v1 v2 v1 v3 v1 v4 v1 v5 A 且v2 v3 v4 v5为T标号 所以修改这四个点的标号 T v2 min T v2 P v1 12 min 0 12 12T v3 min T v3 P v1 13 min 0 16 16T v4 min T v4 P v1 14 min 0 23 23T v5 min T v5 P v1 15 min 0 37 37 3 比较所有具有T标号的点 把最小者改为P标号 T v2 最小 令P v2 12 4 v2为刚得到P标号的点 考察弧 v2 v3 v2 v4 v2 v5 的端点v3 v4 v5 T v3 min T v3 P v2 23 min 16 12 13 16T v4 min T v4 P v2 24 min 23 12 17 23T v5 min T v5 P v2 25 min 37 12 24 36 5 比较所有具有T标号的点 把最小者改为P标号 T v3 最小 令P v3 16 6 考察点v3T v4 min T v4 P v3 34 min 23 16 14 23T v5 min T v5 P v3 35 min 36 16 18 34 7 所有T标号中 T v4 最小 令P v4 23 8 考察点v4T v5 min T v5 P v4 45 min 34 23 15 34 9 只有一个T标号T v5 令P v5 34 计算结束 由上可知 v1到v5的最短路为v1 v3 v5 长度为34 其含义为 最佳更新计划为第一年年初购买新设备使用到第二年年底 第三年年初 第三年年初再购买新设备使用到第四年年底 这个计划使得总的支付最小 其值为34 v1 v3 v2 v7 v5 v4 v6 1 7 1 3 4 4 5 2 5 7 2 练习 求下图中任意两点间的最短路 4 例 某地7个村庄之间的现有交通道路如下图所示 边旁数字为各村庄之间道路的长度 现要在某一村庄修建一所小学 该小学应建在哪个村庄 可使离该村最远的村庄的学生所走的路程最少 该问题可分作两步来考虑 1 求出任意两个村庄之间的最短路长 2 找出每一点到其余各点按照最短路线的最远点 大中取小即可 首先写出权矩阵 用Floyd算法求出任意两点之间的最短路的长度 找出每一点到其余各点按照最短路线的最远点取这些最远距离中的最小者 小学应建在v4村 max 作业 P227习题4 4 覆盖与点独立集 最大流问题 最大流问题是在一个给定网络上求流量最大的可行流 即给一个网络的每条弧规定一个流量的上界 求从点vs到vt的最大流 下图是一个输油管道网 vs为起点 vt为终点 v1 v6为中转站 弧旁的数表示该管道的最大输油量 问题 如何安排 才能使从vs到vt的输油量最大 最大流问题1最大流问题的数学描述1 1网络中的流定义在以V为节点集 A为弧集的有向图G V A 上定义如下的权函数 i L A R为孤上的权函数 弧 i j A对应的权L i j 记为lij 称为孤 i j 的容量下界 lowerbound ii U A R为弧上的权函数 弧 i j A对应的权U i j 记为uij 称为孤 i j 的容量上界 或直接称为容量 capacity iii D V R为顶点上的权函数 节点i V对应的权D i 记为di 称为顶点i的供需量 supply demand 此时所构成的网络称为流网络 可以记为N V A L U D 由于我们只讨论V A为有限集合的情况 所以对于弧上的权函数L U和顶点上的权函数D 可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示 因此L U D有时直接称为权向量 或简称权 由于给定有向图G V A 后 我们总是可以在它的弧集合和顶点集合上定义各种权函数 所以流网络一般也直接简称为网络 定义对于流网络N V A L U D 其上的一个流 flow f是指从N的弧集A到R的一个函数 即对每条弧 i j 赋予一个实数fij 称为弧 i j 的流量 如果流f满足则称f为可行流 feasibleflow 至少存在一个可行流的流网络称为可行网络 feasiblenetwork 约束 1 称为流量守恒条件 也称流量平衡条件 约束 2 称为容量约束 定义 设有向连通图G V E G的每条边 vi vj 上有非负数cij称为边的容量 仅有一个入次为0的点vs称为发点 源 一个出次为0的点vt称为收点 汇 其余点为中间点 这样的网络G称为容量网络 常记做G V E C 对任一G中的边 vi vj 有流量fij 称集合f fij 网络G上的一个流 称满足下列条件的流f为可行流 1 容量限制条件 对G中每条边 vi vj 有0 fij cij 2 平衡条件 对中间点vi 即中间点vi的物资的输入量与输出量相等 对收 发点vs vt 有 即从vs点发出的物资总量等于vt点输入的量 W为网络流的总流量 可行流总是存在的 例如f 0 就是一个流量为0的可行流 最大流问题就是在容量网络中 寻找流量最大的可行流 一个流f fij 当fij cij 则称流f对边 vi vj 是饱和的 否则称f对 vi vj 不饱和 根据弧的流量是否为0 可把弧分为零流弧和非零流弧两类 最大流问题实际是个线性规划问题 但是利用它与图的紧密关系 能更为直观简便地求解 把网络D V E C 的点集V剖分为两个非空集合Vs和Vt 即Vs Vt Vs Vt V 使vs Vs vt Vt 把从Vs指向Vt的弧的全体称为 分离vs和vt的 截集 称截集中所有弧的容量之和为这个截集的容量 简称为截量 分离vs和vt的截集往往不只一个 称其中截量最小的为最小截集 由截集的定义可知 截集是从vs到vt的必经之路 无论去掉哪个截集 从vs到vt就不存在路了 因此任何一个可行流的流量不会超过任何一个截集的容量 因而若能找到一个可行流和一个截集 使得可行流的流量等于这个截集的容量 则该可行流一定是最大流 该截集一定是最小截集 在上图中 若令Vs vs v1 v6 Vt v2 v3 v4 v5 vt 则 截集为 vs v5 v1 v2 v1 v5 v6 v5 v6 v4 截量为3 2 4 2 3 14 设 是网络中从vs到vt的一条链 给 定向为从vs到vt 沿此方向 上的弧可分为两类 一类是与链的方向一致的弧称为正向弧 用 表示正向弧的全体 另一类是与链的方向相反的弧称为反向弧 用 表示反向弧的全体 在上图中 在链 vs v5 v6 v4 v3 vt 中 vs v5 v6 v4 v3 vt v5 v6 v4 v3 增广链 对于可行流f 是一条从vs到vt的一条链 如果 中的弧均为非饱和弧 中的弧均为非零流弧 则称 为从vs到vt的关于f的增广链 定理 最大流量 最小截量定理 在网络N中 从vs到vt的最大流的流量等于分离vs到vt的最小截集的截量 计算网络最大流的方法增广链的实际意义在于沿着这条链存在增大输送能力的潜力 如沿着增广链 1 vs v2 v5 v4 v6 vt 凡是正向弧的流量都增加1 反向弧的流量都减少1 见上图 结果整个网络的流增加了1 即由6增加到7 用这种方法调整后的流仍为可行流 这样就得到了一个寻找最大流的方法 从一个可行流开始 寻找关于这个可行流的增广链 若增广链存在 则可以经过调整 得到一个新的可行流 其流量比调整前的可行流大 重复这个过程 直到不存在增广链时就得到了最大流 下面介绍计算网络最大流的标号算法标号法是由Ford和Fulkerson在1957年提出的设已有一个可行流f 若网络中没有给出可行流 则可设f为零流 标号法可分为两步 一 标号过程在这个过程中 网络中的点或者是标号点 或者是未标号点 每个标号点的标号包含两个部分 第一个标号表明它的标号是从哪一点得到的 以便找出增广链 第二个标号是为确定增广链的调整量 用的 1 给发点vs以标号 0 第二个数值表示从上一标号点到这个标号点的最大允许调整量 vs为发点 不限允许调整量 故为 最大流的一种算法 标号法 2 选择一个已标号的点vi 对于vi的所有未标号的邻点vj 按下列规则处理 若边 vi vj E 且fij0 则令 vj min fji vi 并给vj以标号 vi vj 3 重复 2 直到收点vt被标号或不再有点可标号时为止 若vt得到标号 说明存在一条增广链 转 二 调整过程 若vt未得到标号 标号过程已无法进行时 说明f已是最大流 二 调整过程 1 确定调整量 vt 2 若vt的标号为 vj vt 则以fit 代替fit 若vt的标号为 vj vt 则以fit 代替fit 3 令vj代替vt 返回 2 若vj vs 则去掉所有标号转 一 标号法寻求网络中最大流的基本思想 用标号法寻求网络中最大流的基本思想是寻找可增广轨 使网络的流量得到增加 直到最大为止 即首先给出一个初始流 这样的流是存在的 例如零流 如果存在关于它的可增广轨 那么调整该轨上每条弧上的流量 就可以得到新的流 对于新的流 如果仍存在可增广轨 则用同样的方法使流的值增大 继续这个过程 直到网络中不存在关于新得到流的可增广轨为止 则该流就是所求的最大流 标号法过程 A 标号过程 通过标号过程寻找一条可增广轨 B 增流过程 沿着可增广轨增加网络的流量 这两个过程的步骤分述如下 例 用标号法求下图所示的网络中从vs到vt的最大流量 图中弧旁数值为容量cij 1 图中没有给出初始可行流 可设零流为出初始可行流 如图1 先给vs标以标号 0 2 检查vs的邻点v1 v2可知 vs v1 E 且fs1 0 cs1 10 令 v1 min 10 0 10 给v1以标号 vs 10 用同样的方法给v2以标号 vs 14 见图2 3 检查v1的尚未标号的邻点v3 v4可知 v1 v3 E 且f13 0 c13 10 令 v3 min v1 10 0 min 10 10 10 给v3以标号 v1 10 用同样的方法给v4以标号 v1 10 4 检查v3的尚未标号的邻点v5 v6可知 v3 v5 E 且f35 0 c35 4 令 v5 min v3 4 0 min 10 4 4 给v5以标号 v3 4 对于v6 由于 v6 v3 E 且f63 0 不满足标号条件 检查v4的尚未标号的邻点vt可知 v4 vt E 且f4t 0 c4t 13 令 vt min v4 13 0 min 10 13 10 给vt以标号 v4 10 5 由于vt已得到标号 则存在增广链 标号过程结束 转入调整过程 令 vt 10为调整量 从vt开始 按标号 v4 10 找到v4并用f4t 10代替f4t 由标号 v1 10 找到v1并用f14 10代替f14 再由标号 vs 10 找到vs并用fs1 10代替fs1 调整过程结束 调整后的可行流见图5 去掉所有标号 重新开始标号过程 图5 先给vs标以标号 0 检查vs的邻点v1 v2可知 vs v1 E但fs1 10 cs1 10 不满足标号条件 vs v2 E且fs2 0 cs2 14 令 v2 min 14 0 14 给v2以标号 vs 14 图6 v6 5 用同样的方法可得v6的标号 v2 5 vt的标号 v6 5 令 5为调整量 从vt开始进行调整 调整后的可行流见下图 去掉所有标号 重新开始标号过程 0 vs 9 v2 5 不满足标号条件 反向零流弧 v4 3 去掉所有标号 重新开始标号过程 令 3为调整量 从vt开始进行调整 调整后的可行流见下图 0 v2 2 v3 2 v3 2 v5 2 vs 6 v6 2 令 2为调整量 从vt开始进行调整 调整后的可行流见下图 0 v2 2 v3 2 v3 2 v5 2 vs 6 v6 2 用标号法在得到最大流的同时也得到最小截集 如图中虚线所示 标号点集合为VS 即VS vs v2 未标号点集合为Vt 即Vt v1 v3 v4 v5 v6 vt 最小截集 vs v1 v2 v3 v2 v6 最小截集的意义 最小截集中各弧的容量总和决定了网络的通过能力 为了提高网络的通过能力 就必须增大最小截集中弧的容量 去掉所有标号 重新开始标号过程 0 vs 4 vt未得到标号 但标号过程已无法进行 说明已得到最大流 其值为20 3 5 2 最小费用流问题 上面我们介绍了一个网络上最短路以及最大流的算法 但是还没有考虑到网络上流的费用问题 在许多实际问题中 费用的因素很重要 例如 在运输问题中 人们总是希望在完成运输任务的同时 寻求一个使总的运输费用最小的运输方案 这就是下面要介绍的最小费用流问题 4 6最小费用流问题 最小费用最大流问题 给了一个带收发点的网络 对每一条弧 vi vj 除了给出容量cij外 还给出了这条弧的单位流量的费用bij 要求一个最大流F 并使得总运送费用最小 最小费用最大流的网络图论解法较麻烦 因此下面介绍用线性规划模型结合运筹学软件求解最小费用最大流问题例 某石油公司拥有一个管道网络 使用这个网络可以把石油从采地运送到一些销售点 这个网络的一部分如下图所示 由于管道的直径的变化 它的各段管道 vi vj 的容量cij 单位 万加仑 小时 各段管道单位流量的费用为bij 单位 百元 万加仑 如图 从采地v1向销地v7运送石油 怎样运送才能运送最多的石油并使得总的运送费用最小 求出最大流量和最小费用 弧旁括号中第一个数表示容量cij 第二个数表示单位流量的费用bij 用线性规划模型求解该问题 可分为两个步骤 第一步先求出此网络图中的最大流量F 通过运筹学软件获得以下结果 f12 5 f14 5 f23 2 f25 3 f43 2 f46 1 f47 2 f35 2 f36 2 f57 5 f67 3 最大流量 10 第二步在最大流量F的所有解中 找出一个最小费用的解 下面建立第二步中的线性规划模型如下 仍然设弧 vi vj 上的流量为fij 这时已知网络中最大流量为F 线性规划模型如下 s t 用管理运筹学软件 可求得如下结果 f12 4 f14 6 f25 3 f23 1 f43 3 f57 5 f36 2 f46 1 f47 2 f67 3 f35 2 其最优值 最小费用 145 与前面求最大流的结果对比 f12 5 f14 5 f23 2 f25 3 f43 2 f46 1 f47 2 f35 2 f36 2 f57 5 f67 3最大流量 10 如果把上例的问题改为 每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少 应怎样运送 这就变成了一个最小费用流的问题 一般来说 所谓最小费用流的问题就是 在给定了收点和发点并对每条弧 vi vj 赋权以容量cij及单位费用bij的网络中 求一个给定值f的流量的最小费用 这个给定值f的流量应小于等于最大流量F 否则无解 求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可 在上例中只要把f12 f14 F改为f12 f14 f 6得到了最小费用流的线性规划的模型 4 7分配问题 一 最大匹配例 考虑有n个工人 m件工作的工作分配问题 每个工人能力不同 各能胜任某几项工作 假设每件工作只需一人做 每人只做一件工作 问怎样分配才能使尽可能多的工人有工作 定义 匹配与最大匹配 在二部图G X Y E M是边集E的子集 若M中的任意两条边都没有公共端点 则称M为图G的一个匹配 若不存在另一匹配M1 使得 M1 M M 表示集合M中边的条数 则称M为最大匹配 上例中的问题用图的语言描述如下 用x1 x2 xn表示n个工人 y1 y2 ym表示m项工作 xi yj 表示工人xi能胜任工作yj X x1 x2 xn Y y1 y2 ym 得到一个二部图G X Y E 问题 在图G中找一个边集E的子集M 使得M中的任意两条边没有公共端点 并且边数尽可能的多 即最大匹配 令 则最大匹配问题的线性规划模型为 这里 ij 1 二 最优匹配例4 15 现有4个工人 4台不同的机床 由于工人对各台机床的操作技术水平不同 每个工人在各台机床上完成给定任务所需工时不同 其效率矩阵为 问题 哪个工人操作哪台机床可使总工时最少 工人 机床 1 数学模型对于有n个工人和n项工作的分配问题 社xij 1或0分别表示工人i做 不做工作j 数学模型为 minz s t 2 匈牙利方法 定理4 9 若矩阵W的元素可分成0与非0两部分 则覆盖0元素的直线数等于位于不同行不同列的0元素的最大个数 定理4 8 如果从分配问题效率矩阵W ij 的每一行元素中分别减去 或加上 一个常数ui 从每一列分别减去 或加上 一个常数vj 得到一个新效率矩阵B bij 其中bij ij ui vj 则二者的最优解等价 匈牙利方法 根据定理4 8的方法不断变换效率矩阵W 使其产生尽可能多的0元素 并且始终保持所有元素非负 直到能从变换后的矩阵中找出位于不同行不同列的0元素为止 这些0元对应的xij 1 其余元素对应xij 0的方案为最优解 下面以例4 15说明最优匹配的匈牙利方法的应用 1 变换效率矩阵 2 在B1中寻找位于不同行 不同列的0元 1 检查B1的每行 列 从中找出未加标记的0元最少的行 列 在该行 列 用 标出一个0元 若该行 列 有多个0元 则任意标一个 2 把刚得到的0 所在的行 列中的其余0元划去 用0表示 3 0 0就是有标记的0元 返1 反复进行 直到所有0元都有标记为止 这样得到的0 元一定位于不同行 不同列 如果个数等于n 已符合最优性条件 否则转3 3 找出能覆盖矩阵中所有0元的最少直线集合1 对没有0 的行打 2 对已打 的行中所有0元所在的列打 3 再对打有 的列中所有0 元所在的行打 4 重复2 3 直到得不出新的打 的行 列为止 5 没有打 的行和打 的列就是覆盖所有0元的最少直线集合 4 修改矩阵B1 1 在未被直线覆盖的所有元素中找出最小元素 2 所有打 的行都减去此最小元素 所有打 的列都加上此最小元素 令这个新矩阵为B2 返回2 符合最优条件 总工时29 工人 机床 一般的指派问题在实际应用中 会遇到各种非标准形式的指派问题 通常的处理方法是先将它们转化为标准形式 然后再用匈牙利法求解 1 最大化指派问题设最大化指派问题系数矩阵C cij n n 其中最大元素为m 令矩阵B bij n n m cij n n 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同最优解 例矩阵 的最大元素为c33 16 取m 16 令 2 人数和事数不等的指派问题若人少事多 则添上一些虚拟的 人 这些虚拟的 人 做各事的费用系数可取0 理解为这些费用实际上不会发生 若人多事少 则添上一些虚拟的 事 这些虚拟的 事 被各人做的费用系数同样也取0 3 一个人可做几件事的指派问题若某个人可做几件事 则可将该人化作相同的几个 人 来接受指派 这几个 人 做同一件事的费用系数当然都一样 4 某事一定不能由某人做的指派问题若某事一定不能由某个人做 则可将相应的费用系数取作足够大的数M 例 某商业公司计划开办五家新商店 为了尽早建成营业 商业公司决定由5家建筑公司分别承建 已知建筑公司Ai i 1 2 5 对新商店Bj j 1 2 5 的建造费用的报价 万元 为cij i j 1 2 5 见下表 商业公司应当对5家建筑公司怎样分配建造任务 才能使总的建造费用最少 cij 这是标准形式的指派问题 为了保证工程质量 经研究决定舍弃建筑公司A1和A5 而让技术力量较强的建筑公司A1 A2和A3来承建 根据实际情况 可以允许每家建筑公司承建一家或二家商店 求使总费用最少的指派方案 反映投标费用的系数矩阵为 cij 由于每家建筑公司最多可承建两家新商店 因此 把每家建筑公司化作相同的两家建筑公司 Ai和 i 1 2 3 这样 系数矩阵变为 上面的系数矩阵有6行5列 为了使 人 和 事 的数目相同 引入一件虚工作B6 使之成为标准指派问题的系数矩阵 用匈牙利解法解以C为系数矩阵的最小化指派问题 得最优指派方案为由A1承建B1和B3 A2承建B2 A3承建B4和B5 这样 总的建造费用最省 为4十7十9十8十7 35 万元 工作数量 工人数量 工作的数量的工人的数量相等 工作数量 工人数量 工作的数量的工人的数量不相等 虚工作 4 8网络计划 网络计划技术广泛应用于建筑施工和新产品的研制计划 计算机系统的安装调试及各种大型复杂工程的控制管理 其基本原理 首先是把所要做的工作 哪项工作先做 哪项工作后做 各占用多少时间 以及各项工作之间的相互关系等运用网络图的形式表达出来 其次是通过简单的计算 找出哪些工作是关键的 哪些工作不是关键的 并在原来计划方案的基础上 进行计划的优化 一 PRET网络图 programevaluationandreviewtechnique PERT 网络图又称箭线图 是由带箭头的线和节点组成的 用来表示工作流程的有向 有序的网状图形 绘图符号1 工作 活动 工序