数学建模培训班的图论课件.ppt

河南城建学院 图论及其应用 主讲老师：李德英 数学建模培训班 河南城建学院 你的奖杯有多大，就有多少的汗水和 泪水，把奖杯敲碎后，里面就是你的 眼泪和血汗 天道酬勤 河南城建学院 参考书： 、高随祥图论与网络流理论 高等教育出版社 、王树禾 图论 科学出版社 河南城建学院 1 概论 n图论起源于18世纪。第一篇图论论文是瑞士数 学家欧拉于1736 年发表的“哥尼斯堡的七座桥” 。1847年，克希霍夫为了给出电网络方程而引 进了“树”的概念。1857年，凯莱在计数烷的同 分异构物时，也发现了“树”。哈密尔顿于1859 年提出“周游世界”游戏，用图论的术语，就是 如何找出一个连通图中的生成圈，近几十年来 ，由于计算机技术和科学的飞速发展，大大地 促进了图论研究和应用，图论的理论和方法已 经渗透到物理、化学、通讯科学、建筑学、生 物遗传学、心理学、经济学、社会学等学科中 。 图论简介 konigsberg 七桥问题 是否可以 一笔画？ a b d c dc a b 河南城建学院 1 概论 图与网络是运筹学（operations research） 中的一个经典和重要的分支，所研究的问题涉 及经济管理、工业工程、交通运输、计算机科 学与信息技术、通讯与网络技术等诸多领域。 下面将要讨论的最短路问题、最大流问题、最 小费用流问题和匹配问题等都是图与网络的基 本问题。 河南城建学院 n例1 最短路问题（sppshortest path problem） n一名货柜车司机奉命在最短的时间内将一车货 物从甲地运往乙地。从甲地到乙地的公路网纵 横交错，因此有多种行车路线，这名司机应选 择哪条线路呢？假设货柜车的运行速度是恒定 的，那么这一问题相当于需要找到一条从甲地 到乙地的最短路。 河南城建学院 n例2 公路连接问题 n某一地区有若干个主要城市，现准备修建高速 公路把这些城市连接起来，使得从其中任何一 个城市都可以经高速公路直接或间接到达另一 个城市。假定已经知道了任意两个城市之间修 建高速公路的成本，那么应如何决定在哪些城 市间修建高速公路，使得总成本最小？（最小 生成树 ） 河南城建学院 n例3 指派问题（assignment problem） n一家公司经理准备安排名员工去完成项 任务，每人一项。由于各员工的特点不 同，不同的员工去完成同一项任务时所 获得的回报是不同的。如何分配工作方 案可以使总回报最大？（二部图的匹配 ） 河南城建学院 n例4 中国邮递员问题（cppchinese postman problem） n一名邮递员负责投递某个街区的邮件。 如何为他（她）设计一条最短的投递路 线（从邮局出发，经过投递区内每条街 道至少一次，最后返回邮局）？由于这 一问题是我国管梅谷教授1960年首先提 出的，所以国际上称之为中国邮递员问 题。 河南城建学院 n例5 旅行商问题（tsptraveling salesman problem） n一名推销员准备前往若干城市推销产品 。如何为他（她）设计一条最短的旅行 路线（从驻地出发，经过每个城市恰好 一次，最后返回驻地）？这一问题的研 究历史十分悠久，通常称之为旅行商问 题。 河南城建学院 n例6 运输问题（transportation problem ） n某种原材料有多个产地，现在需要将原 材料从产地运往多个使用这些原材料的工厂 。假定个产地的产量和家工厂的需要量已知 ，单位产品从任一产地到任一工厂的运费已 知，那么如何安排运输方案可以使总运输成 本最低？ 河南城建学院 n上述问题有两个共同的特点：一是它们的目的 都是从若干可能的安排或方案中寻求某种意义 下的最优安排或方案，数学上把这种问题称为 最优化或优化（optimization）问题；二是它 们都易于用图形的形式直观地描述和表达，数 学上把这种与图相关的结构称为（network） 。与图和网络相关的最优化问题就是网络最优 化或称网络优化 （netwok optimization）问题 。所以上面例子中介绍的问题都是网络优化问 题。 河南城建学院 2图的定义与记号 河南城建学院 (3)每条边都是无向边的图称为无向图；每条边都是有向边 的图称为有向图；我们仅讨论无向图和有向图。 (4)不与任何结点邻接的顶点称为孤立点，全为孤立点组成 的图(无向图和有向图均可)称为空图。 (5) 在无向图中两顶点间(包括顶点自身)若多于一条边， 则称这几条边为重边.在有向图中若同始点和同终点的边 多于一条,则称这几条边为重边. 图的定义与记号 河南城建学院 图的定义与记号 河南城建学院 定义2 子图：给定两个无(有)向图 g=（v,e），g=（v,e ）。 (1)若 vv 和 ee，则称 g是g的子图； (2)若 vv，ee，且 gg，则称 g是 g 的真子图； (3)若 v=v 和 ee，则称 g是 g 的生成子图(支撑子图 )。 (4)若子图 g无孤立点且g由e唯一确定，则称g是由边集 e导出的子图； (5)若对子图 g=v,e中任二顶点 u,v,(u,v)e (u,v)e，则称 g是由顶点集v导出的子图(易见:v 导出的子图g是以v为其顶点集,所有在g中同时关联于v 中两点的边为其边集). 图的定义与记号 河南城建学院 图的定义与记号 河南城建学院 3路径问题与连通问题 河南城建学院 定义3 (1) 设 是赋权图g中从u到v的路径，则称 为路径p的权; (2) 在赋权图g中，从顶点u到顶点v的具有最小 权的路 ，称为u到v的最短路。 定义2 (1) 在无向图g中,若存在一条从顶点u到w的路 径, 则称从u到w可达.约定每个结点到自身 可达; (2) 任意两点均有路径的图称为连通图； (3) 起点与终点重合的路径称为圈; (4) 连通的无圈图称为树。 河南城建学院 连通图例 不连通图 河南城建学院 4 4图的矩阵表示图的矩阵表示 河南城建学院 1 3 45 2 关联矩阵示例 右上图的关联矩阵是 右下图的关联矩阵是 1 3 4 2 河南城建学院 河南城建学院 邻接矩阵示例邻接矩阵示例 右上图的邻接矩阵是 右下图的邻接矩阵是 1 3 45 2 1 3 4 2 河南城建学院 1 3 4 2 例 右图的可达矩阵是 河南城建学院 二、图论模型实例分析二、图论模型实例分析 实例一 握手的次数 史密斯先生和他太太邀请四对夫妻参加晚会每个人 到的时候，房间里的一些人都要与别的一些人握手。当 然，每个人都不会与自己的配偶握手，也不会跟同一个 人握手两次。之后，史密斯先生问每个人和别人握了几 次手，他们的答案都不一样。那么，史密斯太太和别人 握了几次手呢? 这个问题具有挑战性的原因是因为它没有一个明显 的起始点，但如果对此建立一个图模型，问题就变得很 简单了。 河南城建学院 握手的次数 分析：从题目我们得到了哪些信息? n史密斯和太太邀请四对夫妻参加晚会房间里共有 10 人; n每个人都不会与自己的配偶握手握手的两个人不 是配偶; n每个人都不会跟同一个人握手两次两个人间的握 手最多是一次; n史密斯先生问每个人和别人握了几次手，他们的答案 都不一样除史密斯先生外，每个人和别人握手的 次数都不一样; n除史密斯先生外，每个人握手的次数最多是8次 ，最少为0次; n房间里除了史密斯先生外的9个人，他们与别人 握手的次数分别为0，1，2，3，4，5，6，7，8次。 河南城建学院 握手的次数 要知道史密斯太太和别人握手的次数，只需确定除史 密斯先生外的9人中哪一个是史密斯太太即可。 根据以上信息，建立图模型： 河南城建学院 握手的次数 由图可知： n8号的配偶是0号； n7号的配偶是1号； n6号的配偶是2号； n5号的配偶是3号； n史密斯太太是4号，所以史密斯太太和别 人握了4次 河南城建学院 实例二 渡河问题 某人带狗、羊、以及蔬菜渡河，一小船除需 人划外，每次只能载一物过河。而人不在场时， 狗要吃羊，羊要吃菜，问此人应如何过河？ 模型构成此问题可化为状态转移问题，用四 维向量（人，狗，羊，菜）来表示状态，当一物 在此岸时相应分量取1，而在彼岸时则取0。 （1）可取状态 人在此岸 人在彼岸 总共有十个可取状态。 河南城建学院 现在用状态运算来完成状态转移。由于摆一次游戏即 改变现有状态，为此再引入一个四维转移向量，用它 来反映摆渡情况用1表示过河，0表示未过河。例如表 示人带狗过河。此状态只有四个允许转移向量： 现在规定状态向量与转移向量（分量） 之间的运算为 渡河问题 河南城建学院 渡河问题 模型求解 通过上面的定义，问题化为由初始状态 出发，经过奇数次上述运算转移为状态 的转 移过程。可用图表示为 河南城建学院 河南城建学院 实例三 循环比赛的名次 1.1 问题 n支球队循环比赛，每场只计胜负，没有平局. 根据比赛结果排出各队名次.图（1）给出了6支 球队的比赛结果，即1队战胜2、4、5、6队，而 输给了3队；5队战胜3、6队，而输给了1、2、4 队等等. 河南城建学院 循环比赛的名次 方法1：寻找按箭头方向通过全部顶点的路径. 312456 146325 无法排名 方法2：计算得分：1队胜4场，2，3队各胜3 场，4，5队各胜2场，6队胜1场.2，3 队，4，5队无法排名.32，45 排名132456合理吗？ 用图论的知识可以解决这个问题. 河南城建学院 循环比赛的名次 1.2 竞赛图及其性质 循环比赛的结果竞赛图：每对顶点之间都有 一条边相连的有向图.名次是由出度由大到小排序。 3个顶点的竞赛图： 名次：1,2,3 (1,2,3)并列 河南城建学院 4个顶点的竞赛图： 名次：1,2,3,4 2,(1,3,4) (1,3,4),2 (1,2),(3,4) 1,2,3,4 循环比赛的名次 河南城建学院 循环比赛的名次 竞赛图的3种形式： n具有唯一的完全路径，如(1) n双向连通图-任一对顶点存在两条有向路径相 互连通，如(4)； n其他，如(2),(3). 竞赛图的性质： n必存在完全路径； n若存在唯一的完全路径，则由它确定的顶 点 顺序与按得分排列的顺序一致，如（1 ）. 双向连通竞赛图的名次排序 河南城建学院 循环比赛的名次 河南城建学院 循环比赛的名次 1.3 模型建立 定义邻接矩阵如下： 故（4）的邻接矩阵为 河南城建学院 循环比赛的名次 记顶点得分向量为 ,则有 1级得分向量 2级得分向量 河南城建学院 循环比赛的名次 1.4 模型求解 利用著名的perron-frobenius定理，素阵a的最大 特征根为正单根 ，对应正特征向量s，且有 (归一化后) 用s排名. 对（4），因 河南城建学院 循环比赛的名次 对于本节开始提出的6支球队循环比赛的结果，有 ： 河南城建学院 循环比赛的名次 所以 ，排出名 次为 。 河南城建学院 课后作业 四名商人各带一个随从乘船渡河，一只小船 只能容纳二人，由他们自己划行。随从们密约， 在河的任一岸，一旦随从的人数比商人多，就杀 人越货。但是如何乘船渡河的大权掌握在商人们 手中。商人们怎样才能安全渡河呢? 河南城建学院 5 euler图和hamilton图 n5.1 基本概念 n定义 经过g的每条边的迹叫做g的euler迹； 闭的euler迹叫做euler回路或e回路；含euler 回路的图叫做euler图。 n直观地讲，euler图就是从一顶点出发每边恰 通过一次能回到出发点的那种图，即不重复地 行遍所有的边再回到出发点。 河南城建学院 n定义 包含g的每个顶点的轨叫做hamilton(哈 密顿)轨；闭的hamilton轨叫做hamilton圈或h 圈；含hamilton圈的图叫做hamilton图。 n直观地讲，hamilton图就是从一顶点出发每顶 点恰通过一次能回到出发点的那种图，即不重 复地行遍所有的顶点再回到出发点。 河南城建学院 neuler回路的fleury算法 n1921年，fleury给出下面的求euler回路的算 法。 nfleury算法： n1. v0v(g)，令w0=v0。 n 2. 假设迹wi=v0e1v1eivi已经选定，那么按 下述方法从e-e1, ,ei中选取边ei+1： 河南城建学院 n（i）ei+1和vi相关联； n（ii）除非没有别的边可选择，否则ei+1不是 gi=g- e1, ,ei的割边(cut edge)。(所谓割边 是一条删除后使连通图不再连通的边)。 n3. 当第2步不能再执行时，算法停止。 河南城建学院 n应用 n邮递员问题 n中国邮递员问题 n一位邮递员从邮局选好邮件去投递，然后返回 邮局，当然他必须经过他负责投递的每条街道 至少一次，为他设计一条投递路线，使得他行 程最短。 n上述中国邮递员问题的数学模型是：在一个赋 权连通图上求一个含所有边的回路，且使此回 路的权最小。 n显然，若此连通赋权图是euler图，则可用 fleury算法求euler回路，此回路即为所求。 河南城建学院 n多邮递员问题： n邮局有k(k2)位投递员，同时投递信件 ，全城街道都要投递，完成任务返回邮 局，如何分配投递路线，使得完成投递 任务的时间最早？我们把这一问题记成 kpp。 河南城建学院 n旅行商（tsp）问题 n一名推销员准备前往若干城市推销产品，然后 回到他的出发地。如何为他设计一条最短的旅 行路线（从驻地出发，经过每个城市恰好一次 ，最后返回驻地）？这个问题称为旅行商问题 。用图论的术语说，就是在一个赋权完全图中 ，找出一个有最小权的hamilton圈。称这种圈 为最优圈。与最短路问题及连线问题相反，目 前还没有求解旅行商问题的有效算法。所以希 望有一个方法以获得相当好（但不一定最优） 的解。 河南城建学院 7 最小生成树及其应用 n定义 无向图g=（v,e）的生成子图t是树,则称t是g的一棵生 成树（支撑树）(不唯一）. n任何连通无向图g至少有一棵生成树. n赋权简单连通无向图g=(v,e,w)的子图 h的权定义为 h 的所 有边的权和.g中权最小的生成树称为最小生成树(对普通简单 连通图不考虑最小生成树). n最小生成树有很强的应用背景,例如:设计联系若干城市的最 短线路通信网;设计供应若干居民点的最短自来水管线路等. n最小生成树的求法：破圈法和避圈法 河南城建学院 a kruskal算法（或避圈法 ） 步骤如下： 1) 选择边e1，使得w(e1)尽可能小； 2) 若已选定边 ，则从 中选取 ，使得: i) 为无圈图， ii) 是满足i)的尽可能小的权， 3) 当第2)步不能继续执行时，则停止. 定理4 由kruskal算法构作的任何生成树 都是最小树. 最小生成树与算法 河南城建学院 例 用kruskal算法求下图的最小树. 在左图中 权值 最小的边有 任取一条 在 中选取权值 最小的边 中权值最小边有 , 从中选 任取一条边 会与已选边构成圈,故停止,得 中选取在中选取 中选取 . 但 与 都 河南城建学院 b 破圈法 任取一个圈，从圈中去掉一条权最大的边（如果 有两条或两条以上的边都是权最大的边，则任意去掉 其中一条）。在余下的图中，重复这个步骤，直到得 到一个不含圈的图为止，这时的图便是最小树。 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 河南城建学院 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 64 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 64 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2v4 v5 v6 1 5 河南城建学院 2 3 4 5 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 v3 v1 v2v4 v5 v6 1 5 河南城建学院 最小生成树实例:有线电视网最优布线问题 单位：100米 1.问题重述: 卫星加密电视的开播,受到大 家欢迎,要想收看加密电视必 须建一套有线电视网我们 考虑这样一个具体问题：设 某市六个个区之的相互距离 如下表所示，试确定表数据 形成的网络中，如何布线能 布线最省？ 1 2 3 4 5 6 1 0 13 51 77 68 50 2 13 0 60 70 67 59 3 51 60 0 57 3 62 4 77 70 57 0 20 55 5 68 67 36 20 0 34 6 50 59 2 55 34 0 河南城建学院 最小生成树实例:有线电视网最优布线问题 .问题求解: 最优布线问题，就是要求任何两地都有链相连，而使 总线路最短，这个问题在图论中也称为最小树题作下 图，其中顶点v1 ，v，v ， v ， v ， v 分别表示两 区之间的距离 v1 v6 v3v5 v4 v2 60 70 20 13 67 59 77 57 55 6851 2 34 36 50 河南城建学院 最小生成树实例:有线电视网最优布线问题 对于上图，我们要找使布线最省的网络模型图论中的破圈法可以解 决这个问题，具体过程如下：在圈v1vvv1中，去掉最长边vv60，同 样去掉圈v1vvv1，vvvv，vvvv，v3 v5vv3，v4v5 v6 v4， v1v3v4v1，v1v6v2v1，v2v5v6v2中最长的边v1v51，v2v470，v3v457， v3v536,v4v655， v1v477， v1v568， v2v659， v2v567，最后构 成的图（如下）就是最省的布线图 13 2 50 34 20 v2 v3 v1 v6 v4 v6 v1 v6 v3 v5 v4 v2 60 70 20 13 67 59 77 57 55 6851 2 34 36 50 河南城建学院 8 最短路径问题及其应用 最短路问题就是从给定的网络图中找出任意两点间 距离最短的一条路，其中距离只是权数的代称（在实际 网络中，权数可指时间、费用等）。如选址、管道铺设 时的选线、设备更新、投资等都可以归给为求最短路的 问题。最短路问题有一个重要而明显的性质（算法思 想）：最短路是一条路径，且最短路的任一段也是最短 路。 求最短路的方法： (1) 求从一点到其余各点间的dijkstra算法; (2) 求任意两点间最短距离的矩阵算法(floyd算法)。 设g为赋权有向图或无向图，g边上的权均非负。 河南城建学院 dijkstra(标号法）的算法：迪克斯特拉 不妨用 表示图中两相邻点i和j的距离；若点i 和j不相邻，则可令 ，显然 ；用 表示从 点s到i点的最短距离。现要求从点到某一点t的最 短路。 dijkstra算法步骤如下： （）从点s出发，因 ，将此值标在s旁，表示此点已标号； （）从s点出发，找出与s点相邻的点中距离最小的一个，设为r， 将 的值标在r旁，表示此点已标； （）从已标号的点出发，找出与这些点相邻的所有未标号点p。 若有 ，则对p点标号； （）重复第三步，一直到t点得到标号为止。 矩阵算法步骤（略） 河南城建学院 例 求图中顶点v0与v5的最短路径. 解 :可以将计算过程用一张表表示出来(见下页表) 算法示例 河南城建学院 由上表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这 样从v5往前追踪,得v0到v5的最短路径为： =v0v1v2v4v3v5. w()=9. 河南城建学院 dijkstra算法的标号法举例 2 10 7 3 64 5 2 10 7 3 64 5 2 2 10 7 3 64 5 2 10 7 3 64 5 10 2 9 5 2 2 5 5 9 9 99 0 0 0 0 河南城建学院 最短路径问题实例：医院选址问题 1.问题重述： 新建居民小区的医院，对该区每一户居民都很重要。如下图是一个新 建居民区的示意图，医院建在哪里为好呢？ v2 v1 v3 v5 v10 v7 v6 v4 v9 v8 9 3 2 1 8 2 7 9 5 6 4 8 1 3 1 6 5 河南城建学院 最短路径问题实例：医院选址问题 在上图中， v1， v ， v10表示各居民点， 边表示两居民点之间的道路，边上的数值表示两居民 点之间的距离（也就是该边的权）. 现在需要我们考虑的问题是在这10个居民点中，何 处作为新建医院的理想地址，以使所建医院到最远的 居民点距离尽可能近（即最远点的病人到医院看病时 走的路尽可能短）。 河南城建学院 2. 问题求解： 显然可以看出,上图是一个连通无向图，记为， . 任取vi v(i=1,2, ,10)，考察vi与中其他顶点间的最 短路（也称为距离）：（vi，v），（vi，v2）， ，（vi，v），把这10个距离中最大的数称为顶 vi 的最大服务距离，记为l(vi). 求出上图中各点间的距离，如下表所示，这样就可以把 每个顶点vi对应的最大服务距离l(vi)求出来. 最短路径问题实例：医院选址问题 河南城建学院 最短路径问题实例：医院选址问题 1 2 3 4 5 6 7 8 9 10 10 5 3 6 5 10 10 9 12 13 25 0 2 3 4 9 6 8 8 9 33 2 0 3 2 7 7 6 9 10 46 3 3 0 5 7 5 6 7 8 55 4 2 5 0 5 5 4 7 8 610 9 7 7 5 0 2 1 4 5 710 6 7 5 5 2 0 1 2 3 89 8 6 6 4 1 1 0 3 4 912 8 9 7 7 4 2 3 0 5 1013 9 10 8 8 5 3 4 5 0 河南城建学院 最短路径问题实例：医院选址问题 注：上表中的，分 别代表 v1， v ，v ， v ， v ， v ， v ， v ， v ， v v1到各顶点的距离就是上表中的第一行各数，它们中最大 的是13，所以l(v1)=13，其它各点的最大服务距离分别为: l(v2)=9， l(v3)=10， l(v4)=8， l(v5)=8 ，l(v6)=10 ，l(v7)=10， l(v8)=9 ，l(v9)=12，l(v10)=13。 由于 ，所以把医院建在v4或v5为较好的选择， 进一步调查，如果居民点v的居民比v5多，那么把医院建在v 最好. 河南城建学院 称g = ( x, y, e )为二部图. 如果x中的每个点都与y中的 每个点邻接, 则称g = ( x, y, e )为完备二部图. 若 f：e r +, 则称g = ( x, y, e, f )为二部赋权图. 定义1 设x , y都是非空有限顶点集, 且x y = , 9二部图的匹配及其应用 河南城建学院 定义3 若匹配m的某条边与点v关联, 则称m饱和 点v, 并且称v是m的饱和点, 否则称v是m的非饱 和点. 定义4 设m是图g的一个匹配, 如果g的每一个点 都是m的饱和点, 则称m是完美匹配；如果g中 没有另外的匹配m0, 使 | m0 | m |, 则称 m是最大匹配. 每个完美匹配都是最大匹配, 反之不一定成立. 二部图的匹配及其应用 河南城建学院 例16： 判断下图的匹配 最大匹配 非完美匹配 完美匹配 二部图的匹配及其应用 河南城建学院 定义5 设m是图g的的一个匹配, 其边在em和m 中交错出现的路, 称为g的一条m交错路. 起点 和终点都不是m的饱和点的m 交错路, 称为 m 增广路. 1957年，贝尔热(berge)得到最大匹配的充要条 件： 定理1 g的一个匹配m是最大匹配的充要条件是 g不包含m 增广路. 二部图的匹配及其应用 河南城建学院 1935年，霍尔(hall)得到下面的许配定理： 定理2 设g = ( x, y, e )为二部图, 则 g存在 饱和x的每个点的匹配的充要条件是 对任意s ,有 | n (s ) | | s | . 其中, n (s ) = v | us, v与u相邻. g存在完美匹配的充要条件是 对任意s 或s 有 | n (s ) | | s | . 二部图的匹配及其应用 河南城建学院 n推论1：若g是k(k0)正则2分图，则g有完美 对集。 n所谓k正则图，即每顶点皆度k的图。 n由此推论得出下面的婚配定理： n定理4 每个姑娘都结识k(k1)位小伙子，每个 小伙子都结识k位姑娘，则每位姑娘都能和她 认识的一个小伙子结婚，并且每位小伙子也能 和他认识的一个姑娘结婚。 河南城建学院 工作安排问题之一 给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. n 个工作人员中每个人能胜任一项或几项工作, 但并不是所有工 作人员都能从事任何一项工作. 比如x1能做y1, y2工作, x2能做 y2, y3, y4工作等. 这样便提出一个问题, 对所有的工作人员能不能都分配一 件他所能胜任的工作？ 二部图的匹配及其应用 河南城建学院 我们构造一个二部图g = ( x, y, e ), 这里 x = x1, x2, , xn,y = y1, y2, , yn, 并且当且仅当工作人员xi胜任工作yj时, xi与yj才相邻. 于是, 问题转化为求二部图的一个完美匹配. 因为 |x|=|y|, 所以完美匹配即为最大匹配. 二部图的匹配及其应用 河南城建学院 例18：求下图完美匹配 hungarian算法： 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 解 取初始匹配m0 =x2 y2 , x3 y3 , x5 y5 给x中m0的两个非饱和点x1,x4都给以标号0和 标记* (如下图所示). 00 * * 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 00 去掉x1的标记*, 将与x1邻接的两个点y2, y3都给以 标号1. 因为y2, y3都是m0的两个饱和点,所以将它们在 m0中邻接的两个点x2, x3都给以相应的标号和标记*. * * 11 *2 3 * 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 00 * 11 *2 3 * 去掉x2的标记*, 将与x2邻接且尚未给标号的三 个点y1, y4, y5都给以标号2. 222 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 00 * 11 23 * 222 因为y1是m0的非饱和点, 逆向返回, 直到x1为0为 止.于是得到m0的增广路x1 y2x2 y1, 记p = x1 y2 , y2x2 , x2 y1. 取m1 = m0p = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则m1是比 m多一边的匹配. 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 0 * 再给x中m1的非饱和点x4给以标号0和标记*, 然后 去掉x4的标记*, 将与x4邻接的两个点y2, y3都给以标号4. 44 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 0 44 因为y2, y3都是m1的两个饱和点, 所以将它们在m1中 邻接的两个点x1, x3都给以相应的标号和标记*. *2 3 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 0 44 *2 3 去掉x1的标记*, 因为与x1邻接的两个点y2, y3都有标号4, 所以去掉x3的标记*. 而与x3邻接的两个点y2, y3也都有标号4, 此时x中所 有有标号的点都已去掉了标记*(如下图所示), 因此m1是 g的最大匹配.没有完美匹配。 二部图的匹配及其应用 河南城建学院 例18：求下图的最大匹配。 匈亚利算法： 注意到s=x1,x3,x4时，n(s)=y2,y3, 所以没有完美匹配。 二部图的匹配及其应用 河南城建学院 定义6 设g = ( x, y, e , f )为完备的二部赋权 图, 若l：x y r + 满足： 对任意xx, yy , l (x) + l ( y ) f (x y), 则称l为g的一个可行点标记, 记相应的生成 子图为gl = ( x, y, el , f ), 这里 el = x ye | l ( x ) + l ( y ) = f (x y). 定理3 设l是完备的二部赋权图g = ( x, y, e , f ) 的可行点标记, 若m *是gl的完美匹配, 则m *是g 的最佳匹配. (权数最大的匹配) 二部图的匹配及其应用 河南城建学院 工作安排问题之二 给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. 如果每个工作人员工作效率不同, 要求工作分配的同 时考虑总效率最高. 二部图的匹配及其应用 河南城建学院 我们构造一个二部赋权图g = ( x, y, e , f ), 这里 x = x1, x2, , xn,y = y1, y2, , yn, f(xi yj )为工作人 员xi胜任工作yj时的工作效率. 则问题转化为：求二部赋权图g的最佳匹配. 在求g 的最佳匹配时, 总可以假设g为完备二部赋 权图.若xi与yj不相邻, 可令f(xi yj )=0. 同样地, 还可虚设 点x或y,使|x|=|y|.如此就将g 转化为完备二部赋权图, 而且不会影响结果. 二部图的匹配及其应用 河南城建学院 例19：求赋权矩阵为 的完备二部赋权图g=(x,y,e,f)的最佳匹配。 可行顶点标号法： 矩阵覆盖法： 分枝定界法： 二部图的匹配及其应用 河南城建学院 矩阵覆盖法： step1：求等价分配矩阵。 step2：求独立零元，画上框。（非同列同行的零） step3：最优判别：达到n个独立零元。停。 step4：求覆盖线： 1）封锁没有画框零元的行，封锁就打； 2）在封锁行中未画框零元的列也封锁； 3）在封锁列中画框零元的行也封锁； 4）未封锁行与封锁列画上覆盖线。 step5：调节分配矩阵：在未覆盖元中选取最大元k， 未覆盖行加k，覆盖列减k。转step2. 二部图的匹配及其应用 河南城建学院 定义1 设g = ( v, e )为有向图, 在v中指定一点 称为发点(记为vs ), 和另一点称为收点(记为vt ), 其 余点叫做中间点. 对每一条边vivje, 对应一个非 负实数cij, 称为它的容量. 这样的g称为容量网络, 简称网络, 记作g = ( v, e, c ) .g中任一边vivj有流 量fij , 称集合f = fij为网络g上的一个流. 10 网络流问题 许多系统包含了流量问题。例如交通系统有车许多系统包含了流量问题。例如交通系统有车 流量，金融系统有现金流，控制系统有信息流等。流量，金融系统有现金流，控制系统有信息流等。 许多流问题主要是确定这类系统网络所能承受的最许多流问题主要是确定这类系统网络所能承受的最 大流量以及如何达到这个最大流量。大流量以及如何达到这个最大流量。 河南城建学院 定义2 满足下述条件的流 f 称为可行流： (容量限制条件) 对每一边vivj, 有0 fij cij ; (平衡条件) 对于中间点vk有fik =fkj , 即中 间点vk的输入量 = 输出量. 如果f 是可行流, 则对收、发点vt、vs有fsi =fjt =wf, 即从vs点发出的物质总量= vt点输入的量. wf称为网络 流 f的总流量. 网络流问题 河南城建学院 一个可行流 f = f ij , 当 f ij = c ij时, 则称流 f 对边vivj是 饱和的; 当f ijc ij时, 则称流 f 对边是非饱和的. 把f ij = 0的边称为零流边, f ij 0的边称为非零流边. 若 为网络中从vs到vt的一条链(有向图中的路), 定义 链的方向是从vs到vt , 边的方向与链的方向相同称为前 向边, 前向边的全体记为 + ; 边的方向与链的方向相 反称为后向边, 后向边的全体记为. 最大流问题最大流问题 河南城建学院 定义3 设f是一个可行流, 是从vs到vt一条链. 如果满足 当vivj+ 时, 0 f ij cij, 即 + 中的每一条边都 非饱和边; 当vivj时, 0 f ij c ij, 即 中的每一条边都 非零边. 则称为从vs到vt的关于f 的可增广链. 最大流问题 河南城建学院 定义4 容量网络g = ( v, e, c ), 若点集v被剖分为两 个非空集合s, s c = v s, vs, vt分属于s, s c. 则把边集 (s, s c ) = vivj | vivje, vis, vjs c 称为g的割集 . 若把一割集的边从网络中去掉, 则从vs到vt便不在相通 , 所以割集是从vs到vt的必经之路.割集(s, s c )中所有 边的容量之和, 称为这个割集的容量, 记为c (s, s c ). 最大流问题 河南城建学院 定理1 设 f 为网络g = ( v, e, c ) 的任一可行流, (s, s c ) 是剖分vs , vt 的任一割集, 则有wf c (s, s c ). 若有可行流 f 和割集 (s, s c ), 使得wf = c (s, s c ), 则f 一定是g的最大流, 而 (s, s c ) 必定是g 中所有割集中容量小的一个, 即最小割集. 例20：给出网络的割。 2 3 4 3 1 2 5 最大流问题 河南城建学院 定理2 (最大流最小割定理) 任一个网络中g中, 从vs到vt的最大流的流量等于分割vs, vt的最小割的 容量. 推论 可行流f是最大流的充要条件是不存在从vs到 vt的(关于f的)可增广链. 最大流问题 河南城建学院 实际问题中,一个网络会出现下面两种情况： 发点和收点都不止一个. 解决的方法是再虚设一个发点vs和一个收点vt ,发 点vs到所有原发点边的容量都设为无穷大, 所有原收 点到收点vt 边的容量都设为无穷大. 网络中除了边有容量外,点也有容量. 解决的方法是将所有有容量的点分成两个点,如点v 有容量cv ,将点v分成两个点v和v“,令 c(vv“ ) = cv . 最大流问题 河南城建学院 例21：求网络的最大流。 探索：单向调整法： 双向调整法：ford-fulkerson算法 最大流问题 河南城建学院 例22： 图6-24表明一个网络及初始可行流, 每条 边上的有序数表示 (c ij , f ij ). 求这个网络的最大 流. 标号算法： 最大流问题 河南城建学院 一般提法： 已知网络g = ( v, e, c ) , 每条边vivje除了已给容 量 cij外, 还给出了单位流量的费用bij (0). 所谓 最小费用流问题就是求一个总流量已知的可行流 f = f ij 使得总费用最小. 当要求f为最大流时, 此问题即为最小费用最大流问题. 最小费用流问题 河南城建学院 例23：求下列网络的最小费用流。 3,1 4,2 3,6 5,24,2 负回路算法： 迭加算法： 最小费用流问题 河南城建学院 定义：一个工程由若干相互独立的活动组成，每 个活动称为工序，我们用顶点表示工序，如果工序 i 完 成之后工序 j 才能启动,则图中有一条有向边(i , j ),其权 wi 表示工序 i 所需的时间。这样得 到的赋权有向图g=（v,e）称为pt图。 pt图必定不存在有向回路。 在pt图中，当起点与终点不唯一时，可增加 两个虚拟结点v0和vn 作为新的起点与终点， v0和 vn表示虚工序，与v0连接的边的权为0，与vn连接 的边的权为原终点工序所需时间。 pt图 河南城建学院 例24 一项工程由13道工序组成, 所需时间(单位： 天)及先行工序如下表所示(p172). 工序序号 a b c d e f g h i j k l m 所需时间 2 6 3 2 4 3 8 4 2 3 2 5 6 先行工序 - a a b c,d d d d g,h g h,e j k 试问这项工程至少需要多少天才能完成? 那些工程不 能延误? 那些工程可以延误? 最多可延误多少天? pt图 河南城建学院 工序序号 a b c d e f g h i j k l m 所需时间 2 6 3 2 4 3 8 4 2 3 2 5 6 先行工序 - a a b c,d d d d g,h g h,e j k 先作出该工程的pt图. a b 2 2 c 6d 3 e 2 f 2 g 2 h 2 k 4 n 3 i8 j 8 4 4 2 l 3 m 2 5 6 虚拟结点 pt图 河南城建学院 这项工程至少需 要多少天才能完成? 就是要求a到n的最长路,此路径称为关键路径. 那些工程不能延误? 那些工程可以延误? 最多可延误 多少天?关键路径上的那些工程不能延误. pt图 河南城建学院 定理 若有向图g中不存在有向回路,则可以将g 的结 点重新编号为u1, u2, , un,使得对任意 的边ui uje(g),都有i j . 关键路径-最长路算法 各工序最早启动时间算法步骤： 对结点重新编号为u1, u2, , un . 赋初值 (u1)= 0. 依次更新 (uj ),j = 2, 3, , n . (uj )= max(ui )+ (ui ,uj )|uiuje(g). 结束. pt图 河南城建学院 此例不必重新 编号，只要按 字母顺序即可. (a)=0, (b)=(c)=2, (d)=8, (e)=max2+3,8+2=10, (f)=(g)=(h)=(d)+2=10, (i)=max(g)+8,(h)+4=18, (j)=(g)+8=18, (k)=max(e)+4,(h)+4=14, (l)=(j)+3=21, (m)=(k)+8=22, (n)=max(f)+3,(i)+2,(l)+5,(m)+6=28. 最早启动时间: pt图 河南城建学院 这项工程至少需要28天才能完成. 关键路径(最长路径): abdekmn abdhkmn 工序a,b,d,e,h,k,m不能延误. 各工序允许延误时间t(uj )等于各工序最晚启 动时间(uj )减去各工序最早启动时间(uj ). 即 t(uj )=(uj )-(uj ). pt图 河南城建学院 最晚启动时间算法步骤(已知结点重新编号)： 赋初值 (un )=(un). 更新 (uj ),j = n - 1, n - 2, , 1. (uj )= min(ui )- (ui ,uj )|uiuje(g). 结束. 根据工序uj允许延误时间t(uj )是否为0,可 判断该工序是否在关键路径上. pt图 河南城建学院 (n)=28, (m)=28-6=22, (l)=28-5=23, (k)=(m)-8=14, (j)=(l)-3=20,(i)=28-2=26, (h)=min(k)-4,(i)-4=10, (g)=min(j)-8,(i)-8=12, (f)=28-3=25, (e)=(k)-4=10, (d)=min(e)-2,(f)-2,(g)-2,(h)-2=8, (c)=(e)-3=7,(b)=(d)-6=2,(a)=0. 最晚启动