运筹学胡运权第五版课件(第6章).ppt

第6章图与网络分析 GraphandNetworkAnalysis 图是一种模型 如公路铁路交通图 水或煤气管网图 通讯联络图等 图是对现实的抽象 用点和线的连接组合表示 6 1图的基本概念和模型 图不同于几何图形 一 基本概念 1 图 graph 由V E构成的有序二元组 用以表示对某些现实对象及其联系的抽象 记作G V E 其中V称为点集 记做V v1 v2 vn E称为边集 记做E e1 e2 em 点 vertex 表示所研究的对象 用v表示 边 edge 表示对象之间的联系 用e表示 网络图 赋权图 点或边具有实际意义 权数 的图 记做N 零图 边集为空集的图 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 特别的 若边e的两个端点重合 则称e为环 若两个端点之间多于一条边 则称为多重边 2 图的阶 即图中的点数 例如右图为一个五阶图 3 若图中边e vi vj 则vi vj称为e的端点 e称为vi vj的关联边 若vi与vj是一条边的两个端点 则称vi与vj相邻 若边ei与ej有公共的端点 则称ei与ej相邻 简单图 无环 无多重边的图 例如 e6 v2 v3 4 点v的次 或度 degree 与点v关联的边的条数 记为dG v 或d v v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 v5 悬挂点次为1的点 如v5 悬挂边悬挂点的关联边 如e8 e8 孤立点次为0的点 偶点次为偶数的点 如v2 奇点次为奇数的点 如v5 5 链 图中保持关联关系的点和边的交替序列 其中点可重复 但边不能重复 路 点不能重复的链 圈 起点和终点重合的链 回路 起点和终点重合的路 连通图 任意两点之间至少存在一条链的图 完全图 任意两点之间都有边相连的简单图 n阶完全图用Kn表示 边数 注意 完全图是连通图 但连通图不一定是完全图 v1 v2 v5 v6 v7 v3 v4 e1 e2 e4 e3 e5 e6 e7 e8 e9 如图 v1 e1 v2 e2 v3 e3 v4 e5 v5 e6 v3 e7 v6 e8 v7 是一条链 但不是路 v1 e1 v2 e2 v3 e7 v6 e8 v7 是一条路 v1 e1 v2 e2 v3 e3 v4 e4 v1 是一个回路 v4 e4 v1 e1 v2 e2 v3 e6 v5 e9 v7 e8 v6 e7 v3 e3 v4 是一个圈 本图是一个连通图 7 已知图G1 V1 E1 G2 V2 E2 若有V1 V2 E1 E2 则称G1是G2的一个子图 若V1 V2 E1 E2且E1 E2 则称G1是G2的一个部分图 6 偶图 二分图 若图G的点集V可以分为两个互不相交的非空子集V1和V2 而且在同一个子集中的点均互不相邻 则图G称为偶图 完全偶图 V1中的每个点均和V2中的每个点相邻的偶图 若完全偶图中V1有m个点 V2有n个点 则该图共有mn条边 注意 部分图是子图 子图不一定是部分图 二 应用 例有甲 乙 丙 丁 戊 己六名运动员报名参加A B C D E F六个项目的比赛 如表中所示 打 的项目是各运动员报名参加比赛的项目 问 六个项目的比赛顺序应如何安排 才能做到使每名运动员不连续地参加两项比赛 甲乙丙丁戊己 项目 人 ABCDEF 解 构造一个六阶图如下 点 表示运动项目 边 若两个项目之间有同一名运动员报名参加 则对应的两个点之间连一条边 A B C D E F A C B F E D 为满足题目要求 应该选择不相邻的点来安排比赛的顺序 或D E F B C A 6 2树图和图的最小部分树 1 树 tree 无圈的连通图称为树图 简称为树 用T V E 或T表示 一 树图的概念 2 树的性质 1 树中必有悬挂点 证明 反证法 设树中任何点的次均不为1 因为树无孤立点 所以树的点的次 2 不妨设树有n个点 记为v1 v2 vn因为d v1 2 不妨设v1与v2 v3相邻 又因为树没有圈 且d v2 2 可设v2与v4相邻 依次下去 vn必然与前面的某个点相邻 图中有圈 矛盾 注意 树去掉悬挂点和悬挂边后余下的子图还是树 2 n阶树必有n 1条边 证明 归纳法 当n 2时 显然 设n k 1时结论成立 当n k时 树至少有一个悬挂点 去掉该悬挂点和悬挂边 得到一个k 1阶的树 它有k 2条边 则原k阶树有k 1条边 即n k时结论也成立 综上 n阶树有n 1条边 3 任何有n个点 n 1条边的连通图是树 证明 反证法 假设n个点 n 1条边的连通图中有圈 则在该圈中去掉一条边得到的子图仍连通 若子图仍有圈 则继续在相应圈中去掉一条边 直到得到无圈的连通图 即为树 但是该树有n个点 边数少于n 1 矛盾 注意 树是边数最多的无圈图 树是边数最少的连通图 在树中不相邻的两个点之间添上一条边 则恰得到一个圈 从树中去掉一条边 则余下的图不连通 3 图的最小部分树 1 部分树 若G1是G2的一个部分图 且G1为树 则称G1是G2的一个部分树 或支撑树 G2 A B C D 5 4 7 3 6 5 5 7 6 G1 A C B D 注意 图G有部分树的必要条件是G是连通图 部分树不是唯一的 2 最小部分树 或最小支撑树 图G为网络图 若T是部分树中权和最小者 则称T是G的最小部分树 或称最小支撑树 二 最小部分树的求法 1 原理 1 图中与点v关联的最短边 即权最小的边 一定包含在最小部分树中 2 将图中的点分成两个互不相交的非空子集 则两个子集之间连线的最短边一定包含在最小部分树中 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 即求图中的最小部分树 例 要在下图所示的各个位置之间建立起通信网络 试确定使总距离最佳的方案 2 求法 方法一 避圈法将图中所有的点分V为V两部分 V 最小部分树中的点的集合V 非最小部分树中的点的集合 任取一点vi加粗 令vi V 其他点在V中 在V与V相连的边中取一条最短的边 vi vj 加粗 vi vj 令vj V 并在V中去掉vj 重复 至所有的点均在V之内 取小边 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分树长Lmin 14 例 要在下图所示的各个位置之间建立起通信网络 试确定使总距离最佳的方案 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分树长Lmin 14 方法二 破圈法 任取一圈 去掉其中一条最长边 在余下的图中重复 1 直至图中没有任何圈为止 去大边 6 3最短路问题 1 最短路问题从已知的网络图中找出两点之间距离最短 即权和最小 的路 2 相关记号 1 dij表示图中两个相邻点i和j之间的距离 即权 易见dii 0约定 当i和j不相邻时 dij 2 Lij表示图中点i和j之间的最短距离 即最小权和 易见Lii 0 即在已知的网络图中 从给定点s出发 要到达目的地t 问 选择怎样的行走路线 可使总行程最短 3 狄克斯屈拉 Dijkstra 标号算法 1 适用范围用于求某两个点之间的最短距离 2 原理最短路上任何片段是最短路 v1v2v3v4 v5 3 思想按离出发点s的距离由近至远逐步标出最短距离Lsi以及最佳行进路线 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 5 例求图中S到T的最短路及最短距离 4 步骤在网络图中求s到t的最短路 第一步从s出发 将Lss 0标记在s旁边的方框内 表示点s已标记 第二步找出与s相邻且距离最小的点 设为r 计算Lsr Lss dsr 并将结果标记在r旁边的方框内 表示点r已标记 同时标记边sr 第三步从已标记的点出发 找出这些点的所有未标记邻点 分别计算已标记点的方框数与其邻点的距离之和 利用 叠加最小 的原则确定下一个被标记点 设为p 并将最小的和标记在p旁边的方框内 表示点p已标记 同时标记相应边 第四步重复第三步 直到t得到标记为止 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 0 2 4 4 7 8 9 14 13 5 9 4 最短路 S A B E D T最短距离 LST 13 例求图中S到T的最短路及最短距离 V1 V2 V3 V4 V5 V6 V7 5 2 2 7 6 7 4 2 1 3 6 例求图中v1到v7的最短路 0 5 2 7 7 6 10 例求图中任意两点之间的最短距离 V1 V2 V3 V4 V6 V7 5 2 2 7 6 7 4 2 1 3 6 4 矩阵算法求任意两点间最短距离的方法 构造任意两点间直接到达的最短距离矩阵记做D 0 dij 0 其中dij 0 dij 注意 D 0 是一个对称矩阵 且对角线上的元素全是0 D 0 其中dij 1 min dir 0 drj 0 i r j dir 0 drj 0 r 构造任意两点间直接到达 或者最多经过1个中间点到达的最短距离矩阵D 1 dij 1 即dij 1 为D 0 中第i行和第j行对应元素之和的最小值 D 1 其中dij 2 min dir 1 drj 1 i r j dir 1 drj 1 r 构造任意两点间最多可经过3个中间点到达的最短距离矩阵D 2 dij 2 即dij 2 为D 1 中第i行和第j行对应元素之和的最小值 D 2 其中dij 3 min dir 2 drj 2 i r j dir 2 drj 2 r 构造任意两点间最多可经过7个中间点到达的最短距离矩阵D 3 dij 3 即dij 3 为D 2 中第i行和第j行对应元素之和的最小值 D 3 D 2 故D 2 中的元素就是图中相应两点之间的最短距离 说明 一般的对于D k dij k 其中dij k min dir k 1 drj k 1 k 0 1 2 3 最多可经过2k 1个中间点 收敛条件 当D k 1 D k 时 计算结束 设网络图有p个点 即最多有p 2个中间点 则2k 1 1 p 2 2k 1 k 1 log2 p 1 k k log2 p 1 1 即计算到k lg p 1 lg2 1 时 计算结束 例 下图中v1 v7表示7个村子 需要联合建立一所小学 已知各村小学生的人数分别为v1 30人 v2 40人 v3 25人 v4 20人 v5 50人 v6 60人 v7 60人 问 学校应建在哪一个村子 可使学生总行程最少 V1 V2 V3 V4 V6 V7 5 2 2 7 6 7 4 2 1 3 6 解 用矩阵算法得到任意两个村子之间的最短距离如下 先将每一行的元素乘以该村子的学生人数 得到小学建在相应村子时 该村学生上学时单程所走的路程 再将每一列的元素累加 得到小学建在相应村子时 七个村子的学生上学时单程所走的总路程 故小学应该建在v6村 v1 S v2 v3 v4 T 6 4网络的最大流 v1 S v2 v3 v4 T 一 基本概念和基本结论 2 图的分类 1 无向图 简称图 记做G V E V E分别为点集和边集 2 有向图记做D V A V A分别为点集和弧集 注意 以下讨论的是有向图 3 弧的容量 简称容量 弧 vi vj 上可通过负载的最大能力 用c vi vj 或cij表示 1 图中两点vi与vj之间的连线有两种情况 1 边 edge 未规定方向的连线 记做 vi vj 其中vi vj称为端点 2 弧 arc 规定方向的连线 记做 vi vj 其中vi称为起点 vj称为终点 4 容量网络 简称网络 每条弧都有容量的网络 8 v1 S v2 v3 v4 T 7 9 9 2 6 5 10 5 例如 5 容量网络中点的分类 发点 源点 用S表示 只出不入 收点 汇点 用T表示 只入不出 中间点 有入有出 注意 任意容量网络总可以转换为只有一个发点和一个收点的情况 6 流 flow 加在网络中弧 vi vj 上的一组负载量 用f vi vj 或fij表示 8 8 v1 s v2 v3 v4 t 7 5 9 4 9 9 2 0 6 1 5 5 10 8 5 4 其中cij fij 该流为可行流 10 网络的最大流 即使V f 达到最大的可行流 8 零流 加在每条弧上的流量全为0 易见 零流一定是可行流 每个容量网络都有可行流 9 总流量 从发点s到收点t的流量 记做V f 7 可行流 记做f 能够在网络中通过的流 必须满足以下两个条件 容量限制条件 对所有弧 0 fij cij 中间点平衡条件 对任何一个中间点 流入量 流出量 12 割的容量 割集中各弧的容量之和 13 最小割 所有割集中容量之和最小的一个割集 11 割集 简称割 一组弧的集合 割断这些弧能使从s到t的流中断 定理 网络的最大流量等于它的最小割集的容量 8 8 v1 s v2 v3 v4 t 7 5 9 4 9 9 2 0 6 1 5 5 10 8 5 4 例如 割集 v1 v3 v2 v4 割的容量 9 9 18 14 前向弧 或正向弧 在从发点s到收点t的一条链中 指向为s到t的弧称为前向弧 记做 16 增广链 对于从s到t的一条链 如果在前向弧上满足流量小于容量 即fij0 即后向弧不为0 则称这样的链为增广链 15 后向弧 或逆向弧 在从发点s到收点t的一条链中 指向为t到s的弧称为后向弧 记做 s t 6 4 5 3 4 4 8 7 这是一条增广链 定理 当网络中不存在增广链时 网络达到最大流状态 二 网络最大流的求法标号算法 Ford Fulkerson标号算法 1 基本思想 寻找增广链 若无增广链 则已经得到最大流和最小割 结束 若有增广链 则改善流量分布 再重复寻找 直到不存在增广链为止 2 点v的标号v x v 其中x是使v得到标号的已标号点 v 是从x到v的流量的最大可调值 标号算法下规定 前向弧是已标号点指向未标号点的弧 后向弧是未标号点指向已标号点的弧 3 步骤 对发点s标号 s 0 从已标号点i出发 看与其相邻的未标号点j之间的弧 对前向弧 若满足fij cij 则对点j标号 i j 其中 j min i cij fij 对后向弧 若满足fji 0 则对点j标号 i j 其中 j min i fji 注 若有多个可标号点 可任选 若出现其他情况 则点j不标号 前向弧不饱和 要标号 后向弧不为0 要标号 当t得到标号时 从t开始沿已标号点用反向追踪法得到增广链 利用 t 调整流量 对前向弧 新流量f ij fij t 对后向弧 新流量f ij fij t 其余弧上的流量不变 去掉所有标号 重复 若标号中断 即t没有得到标号 则该流为所求的网络最大流 此时最小割集为已标号点与未标号点之间的前向弧 结束 否则重复 继续标号 直到收点t得到标号 转 8 8 v1 s v2 v3 v4 t 7 5 9 4 9 9 2 0 6 1 5 5 10 8 0 s 2 v2 2 v1 2 v3 1 v4 1 5 4 cij fij 例求网络的最大流 最大可调量为1 7 6 5 3 9 5 6 0 10 9 8 8 v1 s v2 v3 v4 t 7 6 9 5 9 9 2 0 6 0 5 5 10 9 5 3 0 s 1 v2 1 v1 1 最大流V f 14 最小割集 v3 t v2 v4 割集容量之和 14 标号中断 例某河流中有4座岛屿B C D E与河岸A F之间有数座桥相连 问至少需要炸毁几座桥 才可以中断两岸的交通联系 A B C D E F A B C F E D 2 2 2 1 3 1 1 1 1 解 建立6阶容量网络 弧上的容量表示相应