第7章-图与网络模型课件.ppt

1、第第7章章 图与网络模型图与网络模型主讲：重庆三峡学院主讲：重庆三峡学院 关文忠关文忠n7.1 图的若干示例和基本概念图的若干示例和基本概念n7.2 树图与图的最小支撑树树图与图的最小支撑树n7.3 最短路问题最短路问题n7.4 中国邮递员问题中国邮递员问题n7.5 网络最大流问题网络最大流问题n7.6 最小费用流问题最小费用流问题n本章小结与作业本章小结与作业目录精品文档7.1.1 图的若干示例（1）七桥问题精品文档18世纪德国哥尼斯堡七座桥有世纪德国哥尼斯堡七座桥有（如图（如图a），能否不重复一次），能否不重复一次走完并回到出发地？走完并回到出发地？（a）七桥问题示意图）七桥问题示意图（b

2、）七桥问题简单图）七桥问题简单图1736年，欧拉在圣彼得堡科学院年，欧拉在圣彼得堡科学院作了一次学术报告。在报告中，他作了一次学术报告。在报告中，他证明了鉴别任一图形能否一笔画出证明了鉴别任一图形能否一笔画出的准则，即欧拉定理。的准则，即欧拉定理。“任何一张地图只用四种颜色就能任何一张地图只用四种颜色就能使有共同边界的国家着上不同的使有共同边界的国家着上不同的颜色。颜色。”1852年，英国搞地图着色工作的年，英国搞地图着色工作的格思里，首先提出了四色问题。格思里，首先提出了四色问题。1872年，英国数学家凯利正式向年，英国数学家凯利正式向伦敦数学学会提出这个问题，于伦敦数学学会提出这个问题，于

3、是四色猜想成了世界数学界关注是四色猜想成了世界数学界关注的问题。的问题。美国数学教授哈肯和阿佩尔于美国数学教授哈肯和阿佩尔于1976年年6月月,使用伊利诺斯大学的使用伊利诺斯大学的电子计算机计算了电子计算机计算了1200个小时，个小时，作了作了100亿个判断，终于完成了四亿个判断，终于完成了四色定理的证明。色定理的证明。不过不少数学家认为应该有一种不过不少数学家认为应该有一种简捷明快的书面证明方法。简捷明快的书面证明方法。图的若干示例（2）染色问题精品文档图的若干示例（3）管理问题的图示精品文档A B C E D 有有A、B、C、D、E5个球队，已个球队，已比赛过，就在这两队相应的点之比赛过，

4、就在这两队相应的点之间连一条线间连一条线.若在五支球队比赛中，甲胜乙表若在五支球队比赛中，甲胜乙表示为示为“甲甲乙乙”，则右图表明，则右图表明A三胜一负，三胜一负，B和和E一胜一负，一胜一负，C和和D一胜两负。一胜两负。8种化学药品，不能存放在同一种化学药品，不能存放在同一个库房里的用连线表示。个库房里的用连线表示。运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、边的集合构成图。图论是研究由节点和边所组成图形的数学理论和方法。图是边的集合构成图。图论是研究由节点和边所组成图形的数学理论和方法。图是网络分析的

5、基础，根据具体研究的网络对象（如：铁路网、电力网、通信网网络分析的基础，根据具体研究的网络对象（如：铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。图论在自然科学和社会科学中都方法来研究各类网络结构和流量的优化分析。图论在自然科学和社会科学中都有广泛应用有广泛应用,如在管理中网络合理架设、网络承载能力分析、服务设

6、施布点、匹如在管理中网络合理架设、网络承载能力分析、服务设施布点、匹配问题等。配问题等。图图点与连线的集合点与连线的集合7.1.2 图的基本概念精品文档7.1.2 图的基本概念n图、边、弧、无向图、有向图、基础图图、边、弧、无向图、有向图、基础图n图（图（Graph）由点（）由点（Vertex）和点之）和点之间的连线所构成的集合。不带箭头的间的连线所构成的集合。不带箭头的连线称为边（连线称为边（Edge）；带前头的连线）；带前头的连线称为弧（称为弧（Arc）。点和边的集合称为）。点和边的集合称为无向图，如图无向图，如图a，简称图，用，简称图，用G=V，E表示；点和弧的集合称为有向图，表示；点和

7、弧的集合称为有向图，如图如图b，用，用D=V，A表示。有向图去表示。有向图去掉箭头所形成的无向图称为该有向图掉箭头所形成的无向图称为该有向图的基础图。的基础图。精品文档图av1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图b7.1.2 图的基本概念n端点、关联边、点相邻、边相邻端点、关联边、点相邻、边相邻n若边若边 e=u,vE，则称，则称 u,v是是e 的的端点，称端点，称e 是点是点u或或v的关联边。的关联边。有公共关联边的点称为点相邻；有公共关联边的点称为点相邻；公共端点的边称为边相邻。公共端点的边称为边相邻。n环环，多重边多重边，简单图简单图，多重图多重图 n两个端

8、点重合的边称为环；若两两个端点重合的边称为环；若两个点之间有多于一条的边，称为个点之间有多于一条的边，称为多重边；一个无环、无多重边的多重边；一个无环、无多重边的图称为简单图；一个无环，但允图称为简单图；一个无环，但允许有多重边的图称为多重图。许有多重边的图称为多重图。精品文档图av1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图b图av1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图b7.1.2 图的基本概念n次，奇点，偶点，孤立点，悬挂次，奇点，偶点，孤立点，悬挂点，悬挂边点，悬挂边 n点的关联边的数目称为的点的关联边的数目称为的次次(也也称度或线度

9、称度或线度)，记为，记为d(v)(环在计环在计算时算作两次，称为入次和出算时算作两次，称为入次和出次次)；次为奇数的点称为；次为奇数的点称为奇点奇点；次为偶数的点称为次为偶数的点称为偶点偶点；次为；次为0的点称为的点称为孤立点孤立点；次为；次为1的点称的点称为为悬挂点悬挂点；与悬挂点相边关联；与悬挂点相边关联的边称为的边称为悬挂边悬挂边。精品文档n定理定理n【定理定理1】 图中，所有顶点的次之图中，所有顶点的次之和是边数的和是边数的2倍。倍。n【定理定理2】 任一个图中，奇点的个任一个图中，奇点的个数为偶数。数为偶数。n链，圈，路，回路，连通图链，圈，路，回路，连通图 n点和边的交错序列中，若

10、边各不相点和边的交错序列中，若边各不相同称为同称为链链；封闭的链称为；封闭的链称为圈圈；在链；在链中如果点也各不相同称为中如果点也各不相同称为路路；起点；起点与终点重合的路称为与终点重合的路称为回路回路；任意两；任意两点之间至少能找到一条链的图称为点之间至少能找到一条链的图称为连通图连通图。图av1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6图b7.1.2 图的基本概念精品文档n完全图，子图，支撑图（部分图）完全图，子图，支撑图（部分图） n一个简单图中若任意两点之间均有边相连，称一个简单图中若任意两点之间均有边相连，称这样的图为这样的图为完全图完全图，如图，如图 (e)

11、；图；图=(,)和和=(,) 如果满足如果满足及及，则称，则称 是是的的子图子图（如图（如图a是图是图b的子图）；如果的子图）；如果满足满足=及及，则称，则称 是是的一个支的一个支撑图（或称为部分图），如图撑图（或称为部分图），如图(c)是图是图(a)的的支撑支撑图图。(d)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6 (e)7.1.2 图的基本概念精品文档【例例P131图图7.3】这是一染色问题这是一染色问题,其方法其方法:找出次数最大的点找出次数最大的点,将其将其与不相邻的点组成新的点集与不相邻的点组成新的点集;再从其余的子图中找出次数最大的点再从其余的子图中找出次

12、数最大的点,将其与不相邻的点组成新的点集将其与不相邻的点组成新的点集,直到子图的点集为空直到子图的点集为空.v1v8v2v7v3v6v5v4 , , , , 至少需要至少需要4个库房个库房7.1.2 图的基本概念精品文档课程课程研究生研究生ABCDEF1 2 3 4 5 6 7 8 9 10 7.1.2 图的基本概念n补充例题补充例题:10名研究生参加名研究生参加6门课程的考试，由于选修内门课程的考试，由于选修内容不同，考试门数也不一样，容不同，考试门数也不一样，右表列出了每个研究生应参右表列出了每个研究生应参加考试的课程（打加考试的课程（打的）。的）。规定考试在三天内结束，每规定考试在三天内

13、结束，每天上下午各安排一门。研究天上下午各安排一门。研究生提出希望每人每天最多考生提出希望每人每天最多考一门，又课程一门，又课程A必须安排在必须安排在第一天上午考。课程第一天上午考。课程F安排在安排在最后一门。课程最后一门。课程B只能安排只能安排在下午考。试列出一张满足在下午考。试列出一张满足要求的考试日程表。要求的考试日程表。精品文档7.2 树图与图的最小支撑树n本节主要内容：本节主要内容：n树图的概念与性质树图的概念与性质n最小支撑树的概念与性质最小支撑树的概念与性质n最小支撑树的求法最小支撑树的求法避圈法避圈法n最小支撑树的求法最小支撑树的求法破圈法破圈法精品文档7.2.1 树图的概念和

14、性质精品文档 树图，简称树，记作树图，简称树，记作T(V,E)：是一类简单而十分有用的图，：是一类简单而十分有用的图，其定义是无圈的联通图。其定义是无圈的联通图。树图的概念树图的概念 性质性质1 任何树图必存在悬挂点。任何树图必存在悬挂点。 性质性质2 具有具有p个点的树图的边数恰好为个点的树图的边数恰好为p-1条边。条边。性质性质3 任何具有任何具有p个点、个点、p-1条边的联通图是树图。条边的联通图是树图。性质性质4 树图中任意两点之间恰有一条链。树图中任意两点之间恰有一条链。性质性质5 树图中任意两点之间添加一条边正好构成一个圈。树图中任意两点之间添加一条边正好构成一个圈。树图的性质树图

15、的性质(a)(b)7.2.1 树图的概念和性质精品文档 如果图如果图T=(V,E)是图是图G=(V,E)的支撑图，的支撑图，又是树图，则称又是树图，则称T是是G的一个支撑树（或的一个支撑树（或称为部分树）。称为部分树）。支撑树的概念支撑树的概念 给图给图G的每一条边的每一条边vi,vj,相应地赋予一个相应地赋予一个数数wij,则称这样的图则称这样的图G为赋权图为赋权图 。一个支。一个支撑树所有边的权之和为支撑树的权。撑树所有边的权之和为支撑树的权。赋权图的定义赋权图的定义(a)(b) 如果支撑树如果支撑树T的权的权w(T)是的所有支撑树的权中最小者，则称为的是的所有支撑树的权中最小者，则称为的

16、最小支撑树最小支撑树(minimum spanning tree)。即有。即有w(T*)=min w(T)最小支撑树的定义最小支撑树的定义 【定理【定理3】 图图G有支撑树的充分必要条件有支撑树的充分必要条件为为图图G是是连通的。连通的。 【定理【定理4】 图中任意一点图中任意一点i，若，若i,j是与是与i相邻点中相邻点中权权数最小的，数最小的，则边则边i,j一定包含在该图的最小支撑树内。一定包含在该图的最小支撑树内。 推论推论 :把图的所有点分成把图的所有点分成 两个集合两个集合V和和 CV(CV为为V的补集）的补集），则，则两集合之间具有最小权的边一定包含在最小支撑树内。两集合之间具有最小

17、权的边一定包含在最小支撑树内。最小支撑树的性质最小支撑树的性质7.2.1 树图的概念和性质精品文档7.2.2 最小支撑树的求法避圈法精品文档任选任选vi,使使viV,其余点在其余点在 中中V从从V与与 的的连线中找一条最小边连线中找一条最小边,使其包含在最小支撑树内使其包含在最小支撑树内所有点均在所有点均在V中中?结束结束是是,iiVvV V vV否否ABCDEF872594631【例例P201:6.6】求下图最小支撑树求下图最小支撑树W(T*)=17VV7.2.2 最小支撑树的求法破圈法ABDEF8259631C74任取一个圈任取一个圈,从圈中去掉一条最大的边从圈中去掉一条最大的边(如果有两

18、如果有两条或两条以上的边都是权最大的边条或两条以上的边都是权最大的边,则任意去掉其则任意去掉其中一条中一条).在余下的图中重复这个步骤在余下的图中重复这个步骤,直到不含圈直到不含圈的图为止的图为止,此时的图便是最小树此时的图便是最小树.精品文档取回路取回路ABC，去掉最大边，去掉最大边A,B；取回路取回路BCE，去掉最大边，去掉最大边B,E；取回路取回路BCED，去掉最大边，去掉最大边D,E；取回路取回路BCEFD，去掉最大边，去掉最大边B,DW(T*)=17案例 印第安那州公路规划问题精品文档(1)(2)(3)(4)(5)(1)Gary(2)Fort Wayne(3)Evansvile(4)

19、Terre Haute(5)South Hend13221716458132290201792172901133031642011131965879303196因政治原因不能建造连接因政治原因不能建造连接(1)和和(2)的公路以及连接的公路以及连接(3)和和(5)的公路的公路.如何建造可使总施工长度最短如何建造可使总施工长度最短?123452171645829020179196113W(T*)=4147.3.1 求两点间最短路的Dijkstra标号算法nDijkstra算法的基本思想：算法的基本思想：n假定假定v1v2v3v4是是v1v4的最短路，则的最短路，则v1v2v3是是v1v3的最短路

20、，的最短路， v2v3v4是是v2v4的最短路。的最短路。n换句话说，就是最短路的子集也是最短的。换句话说，就是最短路的子集也是最短的。精品文档7.3.1 求两点间最短路的Dijkstra标号算法Dijkstra标号算法步骤：标号算法步骤：设设Lij为从为从i到到j的最短距离，的最短距离，dij为为i到到j连线距离，发点为连线距离，发点为s收点为收点为t。(1)先给发点先给发点s标号标号Lss=0记为记为(s,0)(2)将已标号点与未标号点分成将已标号点与未标号点分成两个集合两个集合 ，在两个集合的相邻点中找出在两个集合的相邻点中找出 给给p点标号点标号Lsp= Lsr+drp(3) 重复重复

21、第第(2)步，直到收点取得标号步，直到收点取得标号为止。为止。精品文档2444633223322ABCTDEFS02356789结论：最短路径SADT，或SCFT；最短路长：9【例例1】,V V rV pVminsrrpLd,VVp VVp【例例2】 用用Dijkstra方法求点方法求点S到点到点T的最短路及路长。的最短路及路长。056813最短路线最短路线:SACT 或或:SAT最短路长最短路长:13(1)给给S标号标号0(2)V=S,补集补集CV=A,B,C,T,minLSS+DSB,LSS+DSA=0+5,0+6=5给给B标号标号5,S,B加粗加粗(2)V=S,B,CV=A,C,T,mi

22、nLSS+DSA,LSB+DBC=0+6,5+8=6给给A标号标号6,S,A加粗加粗(3)V=S,B,A,CV=C,T,minLSA+DAC,LSA+DAT,LSB+DBC=6+2,6+7,5+6=8给给C标号标号8,A,C加粗加粗(3)V=S,B,A,C,CV=T,minLSA+DAT,LSC+DCT=6+7,8+5=13给给T标号标号13,A,C或或A,T加粗加粗7.3.1 求两点间最短路的Dijkstra标号算法精品文档案例 设备更新问题精品文档1 11 21 11 31 11 41 11 51 11 60 14020minmin 02914041060v vv vv vv vv vv

23、vv vv vv vv vLdLdLdLdLd设备在各年年初的设备在各年年初的价格价格第1年第2年第3年第4年第5年1012131415设备所需要的维修费用设备所需要的维修费用使用年数0-11-22-33-44-5维修费用4691219v1 v2 v3 v4 v5 v6202941602231432332241416171819求费用最小的设备更新计划求费用最小的设备更新计划.Dijkstra标号算法：标号算法：先给先给v1标号标号“0”给给v2标号标号“14”给给v3标号标号“20”01 11 31 11 41 11 51 11 61 22 31 22 41 22 51 22 6020029

24、041060minmin201416142214311443v vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vLdLdLdLdLdLdLdLd141 11 41 11 51 11 61 22 41 22 51 22 61 33 41 33 51 33 60290410601422minmin 14311443201720232032v vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vLdLdLdLdLdLdLdLdLd29给给v4标号标号“29”给给v5标号标号“41”给给v6标号标号“52”

25、20291 11 51 11 61 22 51 2261 33 51 43 61 44 51 44604106014311443minmin412023203229182924v vv vv vv vv vv vv vv vv vv vv vv vv vv vv vv vLdLdLdLdLdLdLdLd411 11 61 22 61 33 61 44 615 650601443minmin 203252292441 19v vv vv vv vv vv vv vv vv vv vLdLdLdLdLd最优路线：最优路线：V1V3V6即第即第1年初购置，第年初购置，第3年初更新，第年初更新，第5年

26、末结束。总费用：年末结束。总费用：52527.3.2 求网络各点之间最短路的矩阵计算法精品文档【例例3】求各点间最短路矩阵求各点间最短路矩阵解解(1)构造邻接矩阵构造邻接矩阵(1)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)min,SBSSSBSAABSBBBSCCBSDDBSEEBSFFBSTTBddddddddddddddddd0,22,0,3,1,14 (1)(0)(0)minijirrjddd(2)计算经过计算经过1个中间点的可达矩阵个中间点的可达矩阵一般地一般地(3)利用递推公式计算经过利用递推公式计算经过k个中间点的个中间点的可达

27、矩阵可达矩阵213226735441SACEBDFT( )002120224203120434340713057506160SABCDEFTSABDCDEFT 案例案例服务设施布点服务设施布点问题问题.假设假设图图中点代表社区中点代表社区,要求在要求在10分钟内分钟内可到达的最少数量的消防站设可到达的最少数量的消防站设置置.v1v2v3v4v5v6v7v8v9v10v11v12484631097697181611141511101668953Dij(0)v1v2v3v4v5v6v7v8v9 v10 v11 v12v10484 999 999 999 999 999 999 999 999v24

28、06 999 999 9999 99918 999 999 999v38603 999710 999 999 999 999 999v44 999309 999 999 999 999 999 999 999v5 999 999 999906 999 9991610 999 999v6 999 9997 999607 9996 999 999 999v7 999910 999 999701116 999 999 999v8 999 999 999 999 999 99911014 99998v9 99918 999 9991661614035 999v10 999 999 999 99910

29、999 999 9993011 999v11 999 999 999 999 999 999 9999511015v12 999 999 999 999 999 999 9998 999 999150解解:(1)建立邻接矩阵建立邻接矩阵.该矩阵为对称矩阵该矩阵为对称矩阵,不不相邻为相邻为,以以999表示表示.(2)利用递推关系求得最短路矩阵利用递推关系求得最短路矩阵(见下见下页页)7.3.2 求网络各点之间最短路的矩阵计算法精品文档Dij(k)v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12v10474 13 14 13 24 20 23 25 32v24068 1

30、7 139 20 18 21 23 28v37603 127 10 21 13 16 18 29v448309 10 13 24 16 19 21 32v5 13 17 12906 13 24 12 10 17 32v6 14 137 10607 186911 26v7 139 10 13 1370 11 13 16 18 19v8 24 20 21 24 24 18 110 14 1798v9 20 18 13 16 126 13 14035 20v10 23 21 16 19 109 16 17308 23v11 25 23 18 21 17 11 189580 15v12 32 28 2

31、9 32 32 26 198 20 23 150 x1x2x3x4x5x6x7x8x9x10 x11x12设设:xi=1表示在表示在vi处设消防站处设消防站; xi=0表示在表示在vi处不设消防站处不设消防站.目标是消防站数量最少目标是消防站数量最少,即即:121minjjzx若若vj处发生火警处发生火警,在在vi(i=1,12) 10分钟内能赶到的分钟内能赶到的(即即dij10)，至少设至少设1个消防站个消防站,即：即：121|10 1jijjxd7.3.2 求网络各点之间最短路的矩阵计算法精品文档7.4 中国邮递员问题精品文档 抽象为图的语言，就是给定一个连通图，在每边上赋予一个非负的权，

32、抽象为图的语言，就是给定一个连通图，在每边上赋予一个非负的权，要求过每边至少一次，并使图的总权最小。要求过每边至少一次，并使图的总权最小。 我国管梅谷教授在我国管梅谷教授在19621962年首年首先提出的，因此在国际上通称为中国邮递员问题。先提出的，因此在国际上通称为中国邮递员问题。中国邮递员问题中国邮递员问题 若网络图上的所有点均为偶点，则邮递员可以走遍所有街道，做到每条若网络图上的所有点均为偶点，则邮递员可以走遍所有街道，做到每条街道只走一次而不重复。街道只走一次而不重复。结论结论1:1: 最短的投递路线具有这样的性质：最短的投递路线具有这样的性质： 有奇点连线的边最多重复一次；有奇点连线

33、的边最多重复一次； 在该网络图的每个回路上，有重复的边的长度不超过回路总长的一半。在该网络图的每个回路上，有重复的边的长度不超过回路总长的一半。 结论结论2:2:解解(1)找出奇点找出奇点(4个个)(2)连接不超过回路长一半的边组成两对连接不超过回路长一半的边组成两对(虚线虚线)(3)虚线重复一次虚线重复一次,其余边只走一次其余边只走一次(有多种走法有多种走法)v37.4 中国邮递员问题精品文档【例1】案例 货场巡视路线精品文档解解(1)找出奇点找出奇点(6个个)(2)连接不超过回路长一半的边组成两对连接不超过回路长一半的边组成两对(虚线虚线)(3)虚线重复一次虚线重复一次,其余边只走一次其余

34、边只走一次(有多种走法有多种走法)7.5 网络最大流问题n在许多系统中在许多系统中，经常会遇到经常会遇到“流量流量”问题，如公交系统中的车问题，如公交系统中的车辆流、乘客流、物资流；金融系统中的资金流；辆流、乘客流、物资流；金融系统中的资金流；InternetInternet中的中的信息流等。使网络通过的流量最大，就是网络最大流问题。信息流等。使网络通过的流量最大，就是网络最大流问题。精品文档右图是联结采油场右图是联结采油场v1和加工厂和加工厂v7的管的管道运输网，每一弧代道运输网，每一弧代(vi,vj)表从表从vi到到vj的运输线，产品经这条弧由的运输线，产品经这条弧由vi运输运输到到vj，

35、弧旁的数字表示这条运输线，弧旁的数字表示这条运输线的最大通过能力的最大通过能力c(vi,vj)。现在要求分。现在要求分析该运输网最大运输能力是多少？析该运输网最大运输能力是多少？若要扩大运输能力，制约运输能力若要扩大运输能力，制约运输能力的关键环节在哪里？的关键环节在哪里？7.5.1 基本概念精品文档n容量网络，弧的容量与流量容量网络，弧的容量与流量n可行流可行流n最大流最小割定理最大流最小割定理n增广链增广链容量网络，弧的容量与流量n容量网络是指对网络上的每条容量网络是指对网络上的每条弧都给定一个最大通过能力。弧都给定一个最大通过能力。n从从vi到到vj的最大通过能力，记的最大通过能力，记为

36、为c(vi,vj)或或cij，称为弧，称为弧vi,vj的的容量。容量。n在容量网络中规定一个发点在容量网络中规定一个发点s和一个收点和一个收点t,其余点称为中间其余点称为中间点。点。n在网络中给弧加载的负载量称在网络中给弧加载的负载量称为弧的流量，记为为弧的流量，记为f(vi,vj)或或fij。n网络的最大流是指网络中从发网络的最大流是指网络中从发点点s到收点到收点t之间允许通过的最之间允许通过的最大流量。大流量。精品文档下图为引例的最大流，下图为引例的最大流，v1为发点，为发点，v7为收点，其他为中间点，图中为收点，其他为中间点，图中各弧旁边的数字表示为各弧旁边的数字表示为“容量容量(流量流

37、量)”。可行流n满足下述条件的流称为可行流：满足下述条件的流称为可行流：n（1）容量限制条件：容量限制条件：0f(vi,vj)c(vi,vj)n（2）中间点平衡条件：中间点平衡条件：kf(vi,vk)=j(vj,vi)n可行流总是存在的，当所有弧的流量可行流总是存在的，当所有弧的流量f(vi,vj)=0，就得到一个可，就得到一个可行流（称为零流）行流（称为零流）精品文档最大流最小割定理 K 5(4) 4(4) 4(0) 5(5) 5(4) 5(5) 6(6) 13(11) 4(2) 9(9) 9(9) 10(9) v1 v2 v3 v4 v5 v6 v7 K n割是指将容量网络的发点和收点分割

38、是指将容量网络的发点和收点分割开，使流中断的一组弧的集合，割开，使流中断的一组弧的集合，如图中虚线如图中虚线KK将网络上的点分割将网络上的点分割成成V和和V两个集合，并有：称弧的集两个集合，并有：称弧的集合，如合，如(V,V)=(v1,v3),(v2,v3),(v2,v3)为为一个割。割的容量是组成它的集合一个割。割的容量是组成它的集合各弧的容量之和，用各弧的容量之和，用c(V,V)表示，表示，即割的容量：即割的容量：n如图割的容量如图割的容量(V,V)=c(v1,v3)+c(v2,v4)+c(v2,v5)=9+6+5=20,容量最小的割容量最小的割 称为最小割，称为最小割，最小割的容量即为网

39、络的最大流。最小割的容量即为网络的最大流。精品文档精品文档( , ) (,)( ,)( ,)iji jV Vc V Vc v v n若从发点到收点能找到一条链，使得所有前向弧均为非饱和弧，若从发点到收点能找到一条链，使得所有前向弧均为非饱和弧，所有的后向弧均为非零流弧，则称该链为一条增广链。如所有的后向弧均为非零流弧，则称该链为一条增广链。如v1v2v5v4v7即是一条增广链。即是一条增广链。 5(5) 4(4) 4(0) 5(5) 5(4) 5(4) 6(6) 13(10) 4(1) 9(9) 9(9) 10(9) v1 v2 v3 v4 v5 v6 v7 增广链精品文档7.5.2 最大流问

40、题Ford-Fulkerson标号算法第第1步：步：先给发点先给发点(0,+)标号的含义是标号的含义是(标号来源标号来源,可调整流量可调整流量.第第2步步 找出新的检查点找出新的检查点列出所有与已标号点相邻的未标号点列出所有与已标号点相邻的未标号点(1)若在弧若在弧(vi,vj)上上,fij0,则给则给j标号标号(vi,(vj),(vj)=min(vi), fij(3)若未标号点若未标号点k有两个以上相邻的已标号点有两个以上相邻的已标号点,为减少迭代次数为减少迭代次数,按按(1)、(2)规则规则分别计算出分别计算出(vj),选取最大的进行标记。选取最大的进行标记。第第3步步 重复第重复第2步，

41、可能出现两种结局：步，可能出现两种结局：(1)标号过程中断，标号过程中断，t得不到标号，记已标号点集合为得不到标号，记已标号点集合为V，未标号点集合为，未标号点集合为V，（V,V）为网络最小割）为网络最小割 。(2)t得到标号，标号值为得到标号，标号值为(t)，按反向追踪法找出一个增广链，在增广链上所，按反向追踪法找出一个增广链，在增广链上所有前向弧流量有前向弧流量 加加(t)；所有后向弧流量减；所有后向弧流量减(t)，其余不变，擦去标号，返回，其余不变，擦去标号，返回第第1步。步。精品文档 5(0) 4(0) 4(0) 5(0) 5(0) 5(0) 6(0) 13(0) 4(0) 9(0)

42、9(0) 10(0) v1 v2 v3 v4 v5 v6 v7 【例1】 用标号法求网络的最大流。精品文档1( ,13)v(0,)5(, 5)v2(, 6)v4(, 5)v 5(5) 4(0) 4(0) 5(0) 5(0) 5(0) 6(5) 13(5) 4(0) 9(5) 9(0) 10(0) v1 v2 v3 v4 v5 v6 v7 (0,)1(, 9)v3(, 5)v6(, 5)v 5(5) 4(0) 4(0) 5(5) 5(0) 5(0) 6(5) 13(5) 4(0) 9(5) 9(5) 10(5) v1 v2 v3 v4 v5 v6 v7 (0,)1(,8)v2(, 5)v5(,

43、4)v 5(5) 4(0) 4(0) 5(5) 5(0) 5(4) 6(5) 13(9) 4(0) 9(9) 9(5) 10(5) v1 v2 v3 v4 v5 v6 v7 (0,)1(, 4)v3(, 4)v4(, 4)v【例1】 用标号法求网络的最大流。精品文档 5(5) 4(0) 4(0) 5(5) 5(4) 5(4) 6(5) 13(9) 4(4) 9(9) 9(9) 10(5) v1 v2 v3 v4 v5 v6 v7 (0,)1(, 4)v2(,1)v5(,1)v4(,1)v6(,1)v 5(4) 4(1) 4(0) 5(5) 5(4) 5(5) 6(5) 13(10) 4(4)

44、9(9) 9(9) 10(6) v1 v2 v3 v4 v5 v6 v7 (0,)1(, 3)v2(,1)v4(,1)v6(,1)v【例1】 用标号法求网络的最大流。精品文档 5(4) 4(2) 4(0) 5(5) 5(4) 5(5) 6(6) 13(11) 4(4) 9(9) 9(9) 10(7) v1 v2 v3 v4 v5 v6 v7 (0,)1(, 2)v( ,)56920c V V最小割(最大流)【例1】 用标号法求网络的最大流。精品文档3(0)2(0)1(0)3(0)2(0)洛杉矶JSDeDL朱诺 西雅图 丹佛 达拉斯(0,)( ,3)J(,2)De( ,3)S3(2)2(2)3(

45、2)(J,1)(S,1)(L,1)1(1)2(1)3(3)最小割最小割案例 航空公司的最大流量精品文档城市城市可着陆可着陆航班数航班数朱诺西雅图(J,S)西雅图洛杉矶(S,L)西雅图丹佛(S,De)洛杉矶达拉斯(L,D)丹佛达拉斯(De,D)32312某航空公司要确定每天可以在阿拉斯加州某航空公司要确定每天可以在阿拉斯加州的朱诺和得克萨斯州的达拉斯之间的转接的朱诺和得克萨斯州的达拉斯之间的转接班机。班机必须在西雅图停留。然后在洛班机。班机必须在西雅图停留。然后在洛杉矶或丹佛停留。由于着陆空间有限，所杉矶或丹佛停留。由于着陆空间有限，所以该航空公司每天在一对城市之间安排的以该航空公司每天在一对城

46、市之间安排的航班数量将受到限制。问每天从朱诺到达航班数量将受到限制。问每天从朱诺到达拉斯航班数量最多可达多少？拉斯航班数量最多可达多少？（2）节点供求平衡限制）节点供求平衡限制（3）流量非负限制流量非负限制fij07.6.1 最小费用流的数学模型*【例例7.14】 图为运输网络图，节图为运输网络图，节点点1为发点，节点为发点，节点5为收点，弧旁为收点，弧旁边的数字是（容量，单位费用）边的数字是（容量，单位费用）。现有。现有8个单位的物资要从个单位的物资要从1运往运往5，试安排费用最小的运输方案。，试安排费用最小的运输方案。 (5,8) (8,7) (2,5) (10,9) (4,9) (3,2

47、) (8,4) 1 2 5 3 4 12132425323445min8729594zfffffff121324253234455,8,3,4,2,10,8fffffff121312322425133234243445254580008ffffffffffffff解解 设设fij表示弧表示弧(i,j)的物流量，可建立该问题的物流量，可建立该问题的的LP模型，其目标是费用最小，即：模型，其目标是费用最小，即：约束条件：约束条件：（1）容量限制，即）容量限制，即精品文档一般情况一般情况cij表示弧表示弧(i,j)的运输能力（容量）；的运输能力（容量）；bij表示弧表示弧(i,j)的的单位运输费用；

48、单位运输费用；si表示节点表示节点i的供应或需求量；的供应或需求量；fij表示弧表示弧(i,j)的的流量，则有供求平衡最小费用流的流量，则有供求平衡最小费用流的LP模型：模型：1111min(1,2,., ). .0( , )nnijijijnnijkiijkijijzb fffs instfci j对所有弧7.6.1 最小费用流的数学模型*精品文档7.6.2 最小费用最大流的标号算法第第1步步 赋初始可行流赋初始可行流零流零流f0 ；第第2步步 构造加权网络构造加权网络 W(fij). （1）对零流弧）对零流弧(i,j)以以bij 加权；加权； （2）对饱和弧）对饱和弧(i,j)更改为反向弧

49、更改为反向弧(j,i) ，以，以bji=-bij 进行加权；进行加权； （3）对）对0fijfk) 。第第4步步 重复第重复第2、3步，直到找不到增广链，所得结果即为最小费用最大步，直到找不到增广链，所得结果即为最小费用最大流。流。精品文档7.6.2 最小费用最大流的标号算法精品文档 (5,8) (8,7) (2,5) (10,9) (4,9) (3,2) (8,4) 1 2 5 3 4 承承【例例7.15】，用标号算，用标号算法求从节点法求从节点1到节点到节点5的最的最小费用最大流。小费用最大流。解解 赋初始流赋初始流0流流,构造容量网络构造容量网络由费用构造加权网络由费用构造加权网络(零流

50、弧以零流弧以bij加权加权,饱和弧构造反向弧以饱和弧构造反向弧以-bij反向加权反向加权,非饱非饱和且非零流以和且非零流以bij和和-bij双向加权双向加权).并求最短路即增广链并求最短路即增广链,在增广链上调整流量。在增广链上调整流量。7.6.2 最小费用最大流的标号算法精品文档7.6.2 最小费用最大流的标号算法精品文档案例7-5 货物配送问题精品文档供应商供应商商品商品价格价格单位单位运价运价到仓库到仓库1路程路程km到仓库到仓库2路程路程km123225002270022300300+4路程路程200+5路程路程500+2路程路程160502004060100供应商供应商1供应商供应商