运筹学课件第8章 图与网络分析

第8章图与网络分析 图与网络模型GraphTheory引言 十八世纪的哥尼斯堡城中流过一条河 普雷 格尔河 河上有7座桥连接着河的两岸和河中的两个小岛 当时那里的人们热衷于这样一个游戏 一个游者怎样才能一次连续走过这7座桥 回到原出发点 而每座桥只允许走一次 没有人想出走法 又无法说明走法不存在 这就是著名的 哥尼斯堡7桥 难题 A B C D 图与网络模型GraphTheory引言 哥尼斯堡7桥 难题最终在1736年由数学家Euler的一篇论文给予了完满的解决 这是图论的第一篇论文 在后来的两百年间图论的发展是缓慢的 直到1936年匈牙利数学家O K nig写出了图论的第一本专著 有限图与无限图的理论 在图论的发展过程中还有两位著名科学家值得一提 他们是克希霍夫和凯莱 克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献 而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究 图论的历史上最具有传奇色彩的问题也许要数著名的 四色猜想 了 历史上许许多多数学猜想之一 它描述对一张地图着色的问题 曾经有一位数学家这样说 对于这个问题 一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它 然后 两人都明白这一问题 但是 两人都无能为力 幸运的是在1970 s终于由美国的两位数学家借助大型计算机将其证明了 图与网络模型GraphTheory图与网络的基本概念 图论与网络分析理论所研究的问题十分广泛 内容极其丰富 正如一位数学家所说 可以说 图论为任何一个包含了某种二元关系的系统提供了一种分析和描述的模型 下面我们来看一个案例 国庆大假期间旅游非常火爆 机票早已订购一空 成都一家旅行社由于信誉好 服务好 所策划的国庆首都游的行情看好 要求参加的游客众多 游客甚至不惜多花机票钱暂转取道它地也愿参加此游 旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题 很快 各办事处将其已订购机票的情况传到了总社 根据此资料 总社要作出计划 最多能将多少游客从成都送往北京以及如何取道转机 下面是各办事处已订购机票的详细情况表 图与网络模型GraphTheory图与网络的基本概念 各办事处已订购机票情况表 成都重庆武汉上海西安郑州沈阳昆明广州北京 成都重庆武汉上海西安郑州沈阳昆明广州北京 105158121030 1061525 10 158 86 148 18 810 82610 图与网络模型GraphTheory图与网络的基本概念 将此问题通过图的模型描述 下图中 点 各城市 带箭头连线 从箭尾城市到箭头城市已订购有机票 带箭头连线旁的数字 机票数量 成 重 武 昆 上 广 西 郑 沈 京 8 郑州办事处已订有的到北京的机票数量 图与网络模型GraphTheory图与网络的基本概念 一 图及其分类和术语1 图论中所研究的图并非几何学中的图 也不是绘画中的图 在这里我们所关心的仅仅是图中有多少个点 点与点之间有无线来连接 也就是说我们研究的是某个系统中的元素 点 以及这些元素之间的某种关系 连线 定义 图 一个图G是一个有序二元组 V E 记为G V E 其中 1 V是一个有限非空的集合 其元素称为G的点或顶点 而称V为G的点集V v1 v2 vn 2 E是V中元素的无序对 vi vj 所构成的一个集合 其元素称为G的边 一般表示为e vi vj 而称E是G的边集 边 无向边 没有方向的连线弧 有向边 带有方向的连线无向图 有向图 简单图 多重图 完全图 二部图 偶图 双图 图与网络模型GraphTheory图与网络的基本概念 子图 真子图 生成子图 点生成子图 边生成子图 点的次 奇次点 偶次点 链 圈 路 回路 赋权图 2 连通图在众多各类图中有一类在实际应用中占有重要地位的图连通图 在图中 任意两点间至少存在着一条链 连通图 不连通图 图与网络模型GraphTheory图与网络的基本概念 3 图与矩阵在图与网络分析的应用中 将面临一个问题 如何分析 计算一个较大型的网络 这当然需借助快速的计算工具 计算机 那么 如何将一个图表示在计算机中 或者 如何在计算机中存储一个图呢 现在已有很多存储的方法 但最基本的方法就是采用矩阵来表示一个图 图的矩阵表示也根据所关心的问题不同而有 邻接矩阵 关联矩阵 权矩阵等 邻接矩阵 对于图G V E V n E m 有n n阶方矩阵A aij n n 其中aij k当且仅当vi与vj之间有条边时0其它 图与网络模型GraphTheory图与网络的基本概念 邻接矩阵 图与网络模型GraphTheory图与网络的基本概念 关联矩阵 对于图G V E V n E m 有m n阶矩阵M mij m n 其中mij 2当且仅当vi是边ej的两个端点1当且仅当vi是边ej的一个端点例 0其它 v1 v2 v3 v5 v4 v8 v6 v7 e1 e2 e3 e4 e6 e5 e7 e9 e12 e10 e11 e8 M mij 101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000 v1v2v3v4v5v6v7v8 e1e2e3e4e5e6e7e8e9e10e11e12 图与网络模型GraphTheory最小树问题 二 树 Tree 和最小树树是图论中一类重要的图 实际中有很多系统的结构都是树 树 连通且不含圈的图 简记为T 下面的说法是等价的 T是一个树 T无圈 且m n 1 T连通 且m n 1 T无圈 但每加一条新的边即出现唯一一个圈 T连通 但每舍去一条边就不连通 T中任意两点 有唯一的一条链相连 T是边数最少的连通图 图的生成树 若G图的一个点生成子图是一个树 则称此树是G图的一个生成树 树的权 若Tk是加权图G的一棵树 则树T的全部边的权之和称为树Tk的权 记为 Tk e e Tk最小树 T 是加权图G的一棵最小树 即 T min Tk k 图与网络模型GraphTheory最小树问题 破圈法 避圈法求生成树 图G 生成树T 生成树T 图与网络模型GraphTheory最小树问题 破圈法 避圈法求最小生成树 图G 生成树T 生成树T 1 5 4 2 4 5 3 1 3 4 4 2 1 5 1 2 1 2 3 1 2 1 1 2 1 2 3 1 2 1 1 2 图与网络模型GraphTheory最短路问题 三 路 Path 和最短路最短路问题是网络分析中应用最广泛的问题之一 尽管前面介绍了用动态规划方法求解 但有时却较困难 此时图论的方法却十分有效 最短路问题的一般描述 G V E 是连通图 图中各边 vi vj 有权lij 表示vi vj间无边 vs vt为图中任意两指定点 求一条路 使其是从vs到vt的所有路中最短 路中各边的权之和最小 的一条路 即 L min lij vi vj 图与网络模型GraphTheory最短路问题 E W Dijkstra算法 标号算法 算法基本思路分析 逐步向外搜索 5 2 1 6 5 8 2 8 9 9 7 2 2 1 2 1 0 X P标号 Y T标号 起点到该点的最短距离 起点到该点的最短距离的上界 2 5 2 7 5 11 12 12 10 5 7 5 6 6 7 9 9 10 10 6 3 3 人 狼 羊 草渡河游戏 一个人带着一条狼 一只羊 一筐白菜过河蛤由于船太小 人一次只能带一样东西乘船过河 狼和羊 羊和白菜不能单独留在同岸 否则羊或白菜会被吃掉 人 M Man 狼 W Wolf 羊 G Goat 草 H Hay 点 vi表示河岸的状态 边 ek表示由状态vi经一次渡河到状态vj 权 边ek上的权定为1 我们可以得到下面的加权有向图 图与网络模型GraphTheory最短路问题 v1 u1 M W G H v2 u2 M W G v3 u3 M W H v4 u4 M G H v5 u5 M G 此游戏转化为在下面的二部图中求从v1到u1的最短路问题 v1 v2 v3 v4 v5 u5 u4 u3 u2 u1 图与网络模型GraphTheory最短路问题 在E W Dijkstra算法中必须满足一个条件 在图G中所有边的权lij 0 若在图G中存在有负权边 当然 这种情形只针对有向图而言 时必须对E W Dijkstra算法加以修改 称为修改的E W Dijkstra算法 2 情况二 wij 0设从V1到Vj j 1 2 t 的最短路长为P1jV1到Vj无任何中间点P1j 1 wijV1到Vj中间最多经过一个点P1j 2 min P1j 1 wij V1到Vj中间最多经过两个点P1j 3 min P1j 2 wij V1到Vj中间最多经过t 2个点P1j t 1 min P1j t 2 wij 终止原则 1 当P1j k P1j k 1 可停止 最短路P1j P1j k 2 当P1j t 1 P1j t 2 时 再多迭代一次P1j t 若P1j t P1j t 1 则原问题无解 存在负回路 例 求下图所示有向图中从v1到各点的最短路 v1 v4 v2 v3 v5 v6 v7 v8 2 5 3 4 6 7 4 2 3 1 3 4 2 wijd t v1 vj v1v2v3v4v5v6v7v8 v1 v2 v3 v4 v5 v6 v7 v8 0 2 5 3 0 2 4 0 6 4 0 0 3 0 7 2 0 3 2 0 t 1t 2t 3t 4t 5t 6 0 2 5 3 0 2 0 3 6 11 0 2 0 3 6 6 15 0 2 0 3 3 6 14 10 0 2 0 3 3 6 9 10 0 2 0 3 3 6 9 10 说明 表中空格处为 4 例设备更新问题 制订一设备更新问题 使得总费用最小 第1年第2年第3年第4年第5年购买费1314161924使用年数0 11 22 33 44 5维修费810131827 解 设以vi i 1 2 3 4 5 表示 第i年初购进一台新设备 这种状态 以v6表示 第5年末 这种状态 以弧 vi vj 表示 第i年初购置的一台设备一直使用到第j年初 这一方案 以wij表示这一方案所需购置费和维护费之和 v1 v2 v3 v5 v6 v4 21 44 32 22 89 62 31 63 45 24 47 34 27 37 32 0 Vs 0 V1 31 V1 44 V1 62 V1 78 V3 这样 可建立本例的网络模型 于是 该问题就可归结为从图中找出一条从v1到v6的最短路问题 用Dijkstra标号法 求得最短路为v1 v3 v6 即第一年初购置的设备使用到第三年初予以更新 然后一直使用到第五年末 这样五年的总费用最少 为78 图与网络模型GraphTheory距离矩阵摹乘法 Dijkstra算法比较简单 但是 对于含有负权弧的网络可能失效 这时 应对算法加以修改 即所谓 修改的Dijkstra算法 下面 介绍一种算法 距离矩阵摹乘法 它适用于任何网络的最短路问题 例如 v1 v3 v4 v2 v6 v5 3 4 2 3 3 2 4 4 1 1 1 6 3 3 3 图与网络模型GraphTheory距离矩阵摹乘法 1 网络的距离矩阵设一网络N中有n个点 其中任意两点vi与vj之间都有一条边 vi vj 其权数为wij 若vi与vj不相邻 则虚设一条边 vi vj 并令其权数wij 距离矩阵W wij 前例中的距离矩阵为 W v1v2v3v4v5v6v1032 4v2 04 41v3 0 16 v43 2 01 v55 03v6 33 0 图与网络模型GraphTheory距离矩阵摹乘法 2 求各点至某点的最短路求vi i 1 2 n 至某点vr的最短路 令 dir k vi走k步达到vr的最短距离 i 1 2 n则有dir 1 wir i 1 2 n dir k min wij djr k 1 i 1 2 n 1 j n 令 dk d1r k d2r k dnr k T k 1 2 图与网络模型GraphTheory距离矩阵摹乘法 矩阵摹乘运算法 dk W dk 1 k 2 3 当dk dk 1 k 2 3 则计算停止 dk中的元素即为各点到vr的最短距离 图与网络模型GraphTheory网络中心和重心问题 一 基本概念网络最短距离矩阵D dij n ndij 表示vi到vj的最短距离 1 网络的中心 令 d vi max dij i 1 2 n 若max d vi d vk 1 i n 1 j n 则称点vk为网络的中心 图与网络模型GraphTheory网络中心和重心问题 2 网络的重心设gi为点vi的权重 i 1 2 n 令 h vj gidij j 1 2 n i 1 n 若max h vj h vr 1 j n 则称点vr为网络的重心 图与网络模型GraphTheory网络中心和重心问题 二 应用例 某地7个村镇之间的现有交通道路如下图 边旁数值为各村镇之间道路的长度 点旁数值为各村镇的小学生人数 现拟在某一村镇建一商店和小学 试问 1 商店应该建在何村 能使各村都离它较近 2 小学应该建在何村 能使各村小学生总的行走路程最短 图与网络模型GraphTheory网络中心和重心问题 v1 v3 v4 v5 v6 v7 v2 7 4 6 4 3 5 7 1 2 3 2 4 2 30 40 45 35 25 20 50 距离 人数 图与网络模型GraphTheory网络中心和重心问题 1 中心问题网络最短距离矩阵如下 j 结论 商店应该建在v4村 图与网络模型GraphTheory网络中心和重心问题 2 重心问题 结论 小学应该建在v5村 第四节最大流问题 如下是一运输网络 弧上的数字表示每条弧上的容量 问 该网络的最大流量是多少 vs v2 v1 v3 v4 vt 4 3 2 3 1 2 2 3 4 图与网络模型GraphTheory网络流问题 定义1 定一个有向图D V E 在V中有一个发点vs和一收点vt 其余的点为中间点 对于每一条弧 vi vj 对应有一个c vi vj 0 cij 称为弧的容量 这样的有向图称为容量网络 记为D V E C 1 网络流 义在弧集合E上的一个函数f f vi vj 称f vi vj 为弧 vi vj 上的流量 简记fij 2 可行流 3 最大流 4 增广链 5 最小截集 2 可行流与最大流 定义2满足下列条件的流称为可行流 1 0 fij cij 2 平衡条件 中间点 fij fji vi vj A vj vi A 发点vs fsj fjs v f vs vj A vj vs A ftj fjt v f vt vj A 收点vt vj vt A 式中v f 称为这个可行流的流量 即发点的净输出量 或收点的净输入量 最大流问题 求一流 fij 满足 0 fij cij v f i s fij fji 0i s t v f i t 且使v f 达到最大 3 增广链 给定可行流f fij 使fij cij的弧称为饱和弧 使fij0的弧称为非零流弧 若 是网络中连接发点vs和收点vt的一条链 定义链的方向是从vs到vt 则链上的弧被分成两类 前向弧 弧的方向与链的方向一致全体 后向弧 弧的方向与链的方向相反全体 定义3设f是一可行流 是从vs到vt的一条链 若 满足下列条件 则称之为 关于流f的 一条增广链 在弧 vi vj 上 0 fij cij在弧 vi vj 上 0 fij cij 4 截集与截量 定义4给定网络D V A C 若点集V被剖分为两个非空集合V1和V1 使vs V1 vt V1 则把弧集 V1 V1 称为是 分离vs和vt的 截集 截集是从vs到vt的必经之路 定义5给定一截集 V1 V1 把截集 V1 V1 中所有弧的容量之和称为这个截集的容量 截量 记为C V1 V1 v f C V1 V1 图与网络模型GraphTheory网络流问题 1 流量 截量定理容量网络上任何一个可行流的流量不超过任何一个截集的截量 2 增广链调整定理在增广链上对可行流进行调整可以得到一个流量更大的可行流 3 最大流定理可行流是最大流的充分必要条件是不存在关于该可行流的增广链 步骤 2 标号过程 1 选取一个可行流 可选择零流弧 从Vs出发 在前向弧上 vi vj 若fij0 则给vj标号 Vi l vj 其中l vj min l vi fji 二 寻找最大流的标号法 FordFulkerson 思想 从一可行流出发 检查关于此流是否存在增广链 若存在增广链 则增大流量 使此链变为非增广链 这时再检查是非还有增广链 若还有 继续调整 直至不存在增广链为止 3 若标号延续到vt 表明得到一条从vs到vt的增广链 转入调整阶段4 否则当前流即为最大流 4 调整过程 令调整量为 l vt 令fij vi vj fij fij vi vj fij vi vj 去掉所有的标号 对新的可行流f fij 重新进入标号过程 可结合下图理解其实际涵义 vs v1 v2 v3 v4 vt 4 4 8 1 4 3 2 2 4 0 2 2 1 1 7 2 9 2 vs v1 vt v4 v2 v3 9 7 5 3 3 2 4 4 5 5 3 1 2 1 6 3 7 7 例求下列网络的最大流与最小截集 解 一 标号过程 则v1的标号为 vs l v1 其中 l v1 min l vs cs1 fs1 min 9 2 2 3 检查v1 在弧 v1 v4 上 f14 7 c14 9 f14 c14 则v4的标号为 v1 l v4 其中 l v4 min l v1 c14 f14 min 2 3 1 2 4 检查v4 在弧 v3 v4 上 f14 1 0 则v3的标号为 v4 l v3 其中 l v3 min l v4 f34 min 2 1 1 5 检查v3 在弧 v3 vt 上 f3t 3 c3t 6 f3t c3t 则vt的标号为 v3 l vt 其中 l vt min l v3 c3t f3t min 1 6 3 1 这样 我们得到了一增广链 如图所示 vs v1 vt v4 v2 v3 9 7 5 3 3 2 4 4 5 5 3 1 2 1 6 3 7 7 0 vs 2 v1 2 v4 1 v3 1 其中 vs v1 v1 v4 v3 vt v3 v4 二 调整过程 取调整量为 1 在 上调整f 在 上 fs1 7 1 8f14 2 1 3f4t 5 1 6 在 上 f43 1 1 0 s 1 v t v v 3 9 8 5 3 3 2 5 5 3 2 2 0 6 4 7 7 在上图中重复上述标号过程 依次给vs v2 v1 v4标号后 由于标号无法继续下去 算法结束 这时的流为最大流 最大流的流量为 v v v 4 4 v f 8 3 11 与此同时 可找到最小截集 V1 V1 其中V1为标号点集合 V1为未标号点集合 弧集合 V1 V1 即为最小截集 此例中 V1 vs v2 v1 v4 V1 v3 vt V1 V1 v1 v3 v4 vt 图与网络模型GraphTheory网络流问题 容量网络N上最大流的标号 Ford Fulkerson 算法 下面 我们采用此算法来求解前面的旅行总社计划问题案例 图与网络模型GraphTheory最大流问题 各办事处已订购机票情况表 成都vs重庆v1武汉v2上海v3西安v4郑州v5沈阳v6昆明v7广州v8北京vt 成都重庆武汉上海西安郑州沈阳昆明广州北京 1015128121030 1061525 10 158 86 148 18 810 82610 图与网络模型GraphTheory最大流问题 发点vs 成都 收点vt 北京 前面已订购机票情况表中的数字即是各边上的容量 允许通过的最大旅客量 当各边上的实际客流量为零时略去不写 以零流作为初始可行流 重 武 昆 上 广 西 郑 沈 京 成 0 标号 但未检查 标号 但且已检查 vs 30 0 30 图与网络模型GraphTheory最大流问题 重 武 昆 上 广 西 郑 沈 京 成 30 0 vs 10 vs 15 vs 12 vs 10 vs 8