图与网络计划评审方法(六七章)jsp

1、2022-3-23-第6章 图与网络分析-1-第六章 图与网络分析 图是一种模型，如公路、铁路交通图， 通讯网络图等。 图示对现实的抽象，以点和线段的连接组合表示。2022-3-23-第6章 图与网络分析-2- 1图的基本概念与模型图的基本概念与模型 2树图和图的最小部分树树图和图的最小部分树 3最短路问题最短路问题 4网络的最大流网络的最大流 5最小费用流最小费用流2022-3-23-第6章 图与网络分析-3-BACD 当地的居民热衷于这当地的居民热衷于这样一个问题：样一个问题：一个漫步者如何能够走过一个漫步者如何能够走过这七座桥，并且每座桥只这七座桥，并且每座桥只能走过一次，最终回到原能走

2、过一次，最终回到原出发地。出发地。尽管试验者很多，尽管试验者很多，但是都没有成功。但是都没有成功。2022-3-23-第6章 图与网络分析-4-4欧拉用欧拉用A A、B B、C C、D D四点表示四点表示河的两岸和小岛，用两点间的联河的两岸和小岛，用两点间的联线表示桥，如右下图所示，该问线表示桥，如右下图所示，该问题可归结为：题可归结为：能否从某一点出发，一笔画能否从某一点出发，一笔画出这个图形，最后回到出发点而出这个图形，最后回到出发点而不重复？即一笔画问题。不重复？即一笔画问题。ACBDBCDA欧拉在欧拉在17861786年发表了年发表了题为题为“依据几何位置依据几何位置的解题方法的解题方

3、法”的的论文，解决了著名的哥尼斯堡论文，解决了著名的哥尼斯堡七桥问题七桥问题欧拉证明了上述图形一笔划是不可能的，欧拉证明了上述图形一笔划是不可能的，因为图中每一个点都只和奇数条线相关联因为图中每一个点都只和奇数条线相关联他的结论是：图形能一笔画的充要条件是图形的奇顶点（连接他的结论是：图形能一笔画的充要条件是图形的奇顶点（连接奇数条线的顶点）的个数为零奇数条线的顶点）的个数为零2022-3-23-第6章 图与网络分析-5- 在实际的生产和生活中，人们为了反映事物之间的关系，在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。常常在纸上用点和线来画出各式各

4、样的示意图。例例 有六支球队进行足球比赛，我们分别用点有六支球队进行足球比赛，我们分别用点v v1 1v v6 6 表表示这六支球队，它们之间的比赛情况，也可以用图反示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知映出来，已知v v1 1 队战胜队战胜v v2 2 队，队，v v2 2 队战胜队战胜v v3 3队，队，v v3 3 队战队战胜胜v v5 5 队，如此等等。这个胜负情况，可以用下图所示队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。的有向图反映出来。2022-3-23-第6章 图与网络分析-6-6在自然界和人类的实际生活中，常用点和点与点之间的在自然界和人类

5、的实际生活中，常用点和点与点之间的联线所构成的图，来反映某些研究对象和对象之间的某种联线所构成的图，来反映某些研究对象和对象之间的某种特定的关系。如：特定的关系。如：为了反映城市之间有没有航为了反映城市之间有没有航班，我们可用右图表示。甲城与班，我们可用右图表示。甲城与乙城，乙城与丙城有飞机到达，乙城，乙城与丙城有飞机到达，而甲、丙两城没有直飞航班。而甲、丙两城没有直飞航班。甲甲乙乙丙丙甲甲乙乙丙丙工人工人ABC工作工作6.1 图的基本概念和模型 对于工作分配问题，我们可能对于工作分配问题，我们可能用点表示工人与需要完成的工作，用点表示工人与需要完成的工作，点间连线表示每个工人可以胜任哪点间连

6、线表示每个工人可以胜任哪些工作如右图所示。些工作如右图所示。2022-3-23-第6章 图与网络分析-7-(v1)赵(v2)钱孙(v3) 李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。2022-3-23-第6章 图与网络分析-8-一、概念（1）图：点V和边E的集合，用以表示对某种现实事物的抽象。记作 G=V,E,V=v1,v2,vn, E=e1,e2,

7、em点：表示所研究的事物对象； 边：表示事物之间的联系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若边e的两个端点重合，则称e为环。（3）多重边：若某两端点之间多于一条边，则称为多重边。 给图中的点和边赋以具体的含义和权值，我们称这样的给图中的点和边赋以具体的含义和权值，我们称这样的图为图为网络图网络图（赋权图）（赋权图）2022-3-23-第6章 图与网络分析-9-9 无向图：无向图：G= V,E1 14 43 32 2e e1 1e e5 5e e6 6e e4 4e e3 3e e2 2e e7 71234V =v ,v,v,v1234567E= e ,e ,e ,e ,

8、e ,e ,e112212323434514613744e= v,v,e = v,v,e = v ,v,e = v,v,e = v,v,e = v,v,e = v ,v2022-3-23-第6章 图与网络分析-10-10有向图：有向图：D= V,A111221333243452464574685395410561167a = v,v,a = v,v,a = v,v,a = v,v,a = v ,v,a = v ,v,a = v ,v,a = v ,v , a = v ,v,a = v ,va = v ,v1234567V= v ,v ,v ,v ,v ,v ,v12311A= a ,a ,a

9、,a324567a1a2a3a4a6a5a7a8a9a10a112022-3-23-第6章 图与网络分析-11-（4）简单图：无环、无多重边的图称为简单图。（5）链：点和边的交替序列，其中点可重复，但边不能重复。（6）路：点和边的交替序列，但点和边均不能重复。（7）圈：始点和终点重合的链。（8）回路：始点和终点重合的路。（9）连通图：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。（10）子图，部分图：设图G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，则称G1是G2的一个子图；若V1=V2，E1E2，则称G1是G2的一个部分图。（11）次：某点的关联边的个数称为

10、该点的次，以d(vi)表示。2022-3-23-第6章 图与网络分析-12-次，奇点，偶点，孤立点次，奇点，偶点，孤立点 某点的某点的次次也称为也称为度、线度度、线度。次为奇数的点称为。次为奇数的点称为奇点奇点，次，次为偶数的点称为为偶数的点称为偶点偶点，次为零的点称为，次为零的点称为孤立点，孤立点，次为次为1的点的点称为称为悬挂点悬挂点。如图：如图：奇点为奇点为 v v5 5 ， v v3 3偶点为偶点为 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立点为孤立点为 v6悬挂点为悬挂点为 v52022-3-23-第6章 图与网络分析-13- 有向图中，以vi

11、为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi) ；vi 点的出次和入次之和就是该点的次。 有向图中，所有顶点的入次之和等于所有顶点的出次之和。图的次: 一个图的次等于各点的次之和。定理定理 图图 中，所有顶点的次之和等于所有边数的中，所有顶点的次之和等于所有边数的2 2倍，倍， 即即G= V,Ev Vd(v)=2q2022-3-23-第6章 图与网络分析-14-链，圈，路，回路，连通图链，圈，路，回路，连通图35264734221,vevevevevev链链4734221,vevevev路路,1335264734221veveveve

12、vevev圈圈子图：子图：部分图部分图注意：注意：部分图也是子图，但子图部分图也是子图，但子图不一定是部分图。不一定是部分图。回路回路1224331,v e v e v e v15（1 1）开链和闭链：如果）开链和闭链：如果 ，则该链称为开链；如果，则该链称为开链；如果 ，则该链称为闭链（或称为圈）。则该链称为闭链（或称为圈）。（2 2）简单链和初等链：如链内所含的边均不相同，称之为简单链；如）简单链和初等链：如链内所含的边均不相同，称之为简单链；如链内所含的点均不相同，称之为初等链。链内所含的点均不相同，称之为初等链。 如：如：1niivv1niiv = v12345367v ,v,v,v,

13、v,v,v,v是简单链，是简单链，12367v ,v,v,v,v是初等链，是初等链，12341v ,v,v,v,v是初等圈，是初等圈，412357634v,v ,v,v,v,v,v,v,v是简单圈，是简单圈，1243567e1e2e3e8e4e7e6e5e916 赋权图赋权图：设图：设图 , ,若对其边集若对其边集E E定义了一个实值函数定义了一个实值函数 ， , ,则称该图为一个赋权图。记作则称该图为一个赋权图。记作 。 称称 为边为边 的权。的权。 如某工厂内连接六个车间的道路网如入所示，已知每条路长，要求沿道路如某工厂内连接六个车间的道路网如入所示，已知每条路长，要求沿道路架设连接六个车

14、间的电话线路，使电话总长最短。架设连接六个车间的电话线路，使电话总长最短。123456652715344左图为一赋权图左图为一赋权图最优解：如红线所示，最优解：如红线所示，电话总长电话总长15个单位。个单位。红线所示为图的最小红线所示为图的最小支撑树支撑树G= V,Eijijw v ,v, v ,vEG= V,E,ijw v ,vijv ,v17 网络图：网络图：若若 为一赋权图为一赋权图 ，并在其顶点集合，并在其顶点集合V V中指中指定了起点（或称发点）和终点（或称收点），其余的点为中间点，这样定了起点（或称发点）和终点（或称收点），其余的点为中间点，这样的赋权图称为网络图（简称网络）。记作

15、的赋权图称为网络图（简称网络）。记作 。 网络一般是连通的赋权图。网络一般是连通的赋权图。 若一个网络图中的每条边都是有向的弧，则称之为有向网络，记作若一个网络图中的每条边都是有向的弧，则称之为有向网络，记作 G= V,E,N= V,E,N= V,A,9102015714192562022-3-23-第6章 图与网络分析-18-二、图的模型 例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？甲 乙 丙 丁 戊 己项目人A B C D

16、 E F 2022-3-23-第6章 图与网络分析-19-建立模型：解：项目作为研究对象，排序。设 点：表示运动项目。边：若两个项目之间无无同一名运动员参加。ABCDEFACDEFBAFEDCBACBFEDAFBCDE顺序：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶

17、点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如，就是一个符合要求的考试课程表。2022-3-23-第6章 图与网络分析-24-6.2 树图和图的最小部分树（1）树图： 无圈的连通图称为树图，简称为树。记为T（V，E）一、树图的概念树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。AB CDEF GH运动员 某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科

18、销售科检验科检验科动力科动力科2022-3-23-第6章 图与网络分析-27-（2）树图的性质性质1：任何树中必存在次为1的点。性质2：具有n个顶点的树的边数恰好为n-1条。性质3：任何具有n个点、n-1条边的连通图必为树图。比如有六个顶点的树有比如有六个顶点的树有6 6种种2022-3-23-第6章 图与网络分析-28-性质4：树是边数最多的无圈连通图。在树中任加一 条边，就会形成圈。性质5：树是边数最少的连通图。在树中任减一条边，则不连通。二、图的最小部分树：二、图的最小部分树：1图的部分树：若G1是G2的一个部分图，且为树图，则称G1是G2的一个部分树。G2：ABCD547365576G

19、1：ACBD2022-3-23-第6章 图与网络分析-29-2图的最小部分树：树枝总长为最短的部分树称为图的最小部分树（或最小支撑树） 。树枝：树图中的边称为树枝。2022-3-23-第6章 图与网络分析-34-三、最小部分树的求法定理1：图中任一个点i，若j是与i相邻点中距离最近的点，则边i，j一定在其最小部分树内。推论：将图中所有的点分成V和V两个集合，则两个集合之间连线最短的一个边一定包含在最小部分树内。2022-3-23-第6章 图与网络分析-35-SABCDET252414317557最小部分树长Lmin=14例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最佳的方案。2

20、022-3-23-第6章 图与网络分析-36-1. 避圈法：将图中所有的点分V为V两部分，V最小部分树内点的集合V非最小部分树内点的集合 任取一点vi加粗，令viV， 取V中与V相连的边中一条最短的边(vi,vj)， 加粗(vi,vj)，令vjV 重复 ，至所有的点均在V之内。2. 破圈法： 任取一圈，去掉其中一条最长的边， 重复，至图中不存在任何的圈为止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5树与图的最小树部分树2022-3-23-第6章 图与网络分析-40-SABCDET252414317557最小部分树长Lmin=1437

21、49346321Min C(T)=12Min C(T)=15254173314475答案：6.3 最短路问题 如何用最短的线路将三部电话连起来？ 此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。ABCABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题 问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、投资、

22、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。2022-3-23-第6章 图与网络分析-45- 在图示的网络图中，从给定的点S出发，要到达目的地T。问：选择怎样的行走路线，可使总行程最短？方法：Dijkstra（D氏）标号法按离出发点的距离由近至远逐渐标出最短距离和最佳行进路线。S1求某两点间最短距离的D（Dijkstra）氏标号法2472022-3-23461. 设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =，显然 dii =0。 Dijkstra 算法假设：基本思路：如果 v1 v2 v3 v4 是

23、 v1 v4 的最短路径，则 v1 v2 v3 一定是 v1 v3 的最短路径。 v2 v3 v4 一定是 v2 v4 的最短路径。2. 设 Lsi 表示从 s 点到 i 点的最短距离。2022-3-2347Dijkstra 算法步骤：1. 对起始点 s ，因 Lss =0 ，将 0 标注在 s 旁的小方框内，表示 s 点已标号；2. 从点 s 出发，找出与 s 相邻的点中距离最小的一个，设为 r ，将 Lsr = Lss+ dsr 的值标注在 r 旁的小方框内，表明点 r 也已标号；3. 从已标号的点出发，找出与这些点相邻的所有未标号点 p ，若有 Lsp =min Lss+ dsp , L

24、sr+ drp ，则对 p 点标号，并将 Lsp 的值标注在 p 点旁的小方框内；4. 重复第 3 步，直到 t 点得到标号为止。求从起始点 s 到终止点 t 的最短路径。2022-3-2348例. 求下图中从 v1 到 v7 的最短路。解： (1) 从 v1 点出发，对 v1 点标号，将 L11=0 标注在 旁的小方框内，令 v1V，其余点属于 ；V2022-3-2349L1r = min 0+d12 , 0+ d13 =min5,2=2= L13(2) 同 v1 相邻的未标号点有v2 、 v3 ，2022-3-2350对 v3 标号，将 L13 的值标注在v3 旁的小方框内；将( v1,

25、v3) 加粗，并令 Vv3 V，VvV3。2022-3-2351L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12(3) 同 v1 , v3 相邻的未标号点有v2 、 v4 、 v6 ，2022-3-2352对 v2 标号，将 L12 的值标注在 v2 旁的小方框内；将( v1, v2) 加粗，并令 Vv2 V，VvV22022-3-2353L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16。(4) 同 v1 , v2 ,

26、v3 相邻的未标号点有v4 、 v5、 v6 ，2022-3-2354对 v6 标号，将 L16 的值标注在 v6 旁的小方框内；将( v3, v6) 加粗，并令 Vv6 V，VvV62022-3-2355L1p = min L12+d25 , L12+d24, L13+d34 , L16+d64 , L16+d65 , L16+d67 =min5+7, 5+2, 2+7, 6+2, 6+1, 6+6 = 7 = L14 = L15(5) 同 v1 , v2 ,v3 , v6 相邻的未标号点有v4 、 v5、 v7 ，2022-3-2356对 v4 , v5 同时标号，将 L14 = L15

27、的值标注在 v4, v5 旁的小方框内；将( v2, v4), ( v6, v5) 加粗，并令Vv4v5V，VvvV54,2022-3-2357L1p = min L15+d57 , L16+d67 =min7+3,6+6=10= L17(6) 同 v1 , v2 ,v3 , v4, v5, v6 相邻的未标号点只有 v7 ，2022-3-2358 对 v7 标号，将 L17 的值标注在 v7 旁的小方框内；将( v5, v7) 加粗。图中粗线表明从点 v1 到网络中其它各点的最短路，各点旁的数字就是点 v1 到各点的最短距离。2022-3-23-第6章 图与网络分析-59-SABCDET25

28、241431755702447891413594 最短路线：S AB E D T最短距离：Lmin=13 练习： 1. 用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：6521vvvv61n 逐次逼近算法逐次逼近算法 DijkstraDijkstra算法只适用于所有算法只适用于所有 的情形，当赋权有向图中存在的情形，当赋权有向图中存在负权时，则算法失效。负权时，则算法失效。例如在右图所示的赋权有向图中，例如在右图所示的赋权有向图中，用用DijkstraDijkstra算法得算法得 到到 的最短路的的最短路的权是权是5.5

29、.但这里显然不对；但这里显然不对； 因为因为 到到 的最短路是的最短路是 ，权为，权为3 3。 当当 存在负权时，可采取逐次逼近算法来求解最短路存在负权时，可采取逐次逼近算法来求解最短路。 不妨设从任一点不妨设从任一点 到任一点到任一点 都有一条弧，如果都有一条弧，如果则添加弧则添加弧 ，且令，且令 。 如果为同一顶点，则如果为同一顶点，则 。 ijw01v3v123vvv1v3v75-4231ivijw jvD= V,A,ijija =(v ,v )Aijija =(v ,v )ii= 0, i=1,2,pw62 由最优性原理，若令由最优性原理，若令 为从为从 到到 的最短距离，则必满足如的

30、最短距离，则必满足如下方程：下方程： ，其中，其中P为为D的点数。的点数。 由此可得如下递推公式：由此可得如下递推公式： 其中其中 表示从表示从 走一步直接到达走一步直接到达 的最短距离，的最短距离， 表示从表示从 走走t t步到达步到达 的最短距离。为迭代步数。的最短距离。为迭代步数。 若第若第k k步，对所有步，对所有 ，有，有 则则 为为 到任一点到任一点 的最短路权。的最短路权。 sjd v ,vsvjvsjsiiji=1,2,pd v ,v= mind v ,v+ws到到j 的最短路的最短路s s到到i的最短路的最短路i j 1sjsjdv ,v= , j1,2,p;w tt-1sj

31、siiji=1,2,pdv ,vmindv ,v +w 1sjdv ,v tsjdv ,vsvjv kk-1sjsjdv ,v=dv ,vj1,2,p ksjdv ,vsvjvsvjv63解：迭代初始条件为：解：迭代初始条件为：有有 第二步迭代：第二步迭代：用表表示全部计算过程。用表表示全部计算过程。 1sjsjdv ,v=w 111112111314111516111718dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3, dv ,v=+ , dv ,v=+ ,dv ,v=+ , dv ,v=+ .例例 求所示赋权有向图中从求所示赋权有向图中从 到各点的最短路。

32、到各点的最短路。11-1-1-2-3-3-56318-527212345678 21sjsiijidv ,v= min dv ,v+w, j=1,2,81-11v640-5-350-1-1710110-1-73208-2-21 1-5-50-3-5-1206003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为） 111111121314dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3 6560-5-3-550-1-1-17101-310-1-7-73208-2-2-21

33、1-5-50-3-5-5-12060003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为）66660-5-3-5-550-1-1-1-17101-3-310-1-7-7-73208-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为）67当时当时表明已得到从表明已得到从 到各点的最短路的权，即表中最后一列数。到各点的最短路的权，即表中最后一列数。如

34、果需要知道点到各点的最短路径，可以采用如果需要知道点到各点的最短路径，可以采用“反向追踪反向追踪”的办法。的办法。比如已知，则寻找一点，使比如已知，则寻找一点，使记下，再考察寻找一点，使记下，再考察寻找一点，使记下，直至达到为止本例中记下，直至达到为止本例中因为因为由记下由记下由记下由记下因为因为 一步可达，所以最短路径一步可达，所以最短路径 431j1jdv ,v=dv ,vj=1, 2,8t=41v1v1jd v ,v1kkj1jd v ,vwd v ,v1iik1kd v ,vwd v ,vkj(v ,v )1kd v ,v,ik(v ,v )1vivkv18d v ,v=6166818

35、d v ,v+w=(-1)+7=6=d v ,v68(v ,v )133616d v ,v+w =(-2)+1= -1 =d v ,v36(v ,v )13d v ,v=21368vvvv68660-5-3-5-550-1-1-1-17101-3-310-1-7-7-7320-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为）69例例 设备更新问题。某企业使用一台设备，在每年年初，都要决定设备更新问题。某企业使用一台设备，在每年年初，都要

36、决定是否更新。若购置新设备，要付购买费；若继续使用旧设备，则支是否更新。若购置新设备，要付购买费；若继续使用旧设备，则支付维修费用。试制定一个付维修费用。试制定一个5 5年更新计划，使总支出最少。年更新计划，使总支出最少。 若已知设备在各年的购买费及不同机器役龄时的残值和维修费若已知设备在各年的购买费及不同机器役龄时的残值和维修费，如下表所示：，如下表所示：第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 购买费购买费 11111212131314141414机器役龄机器役龄 0-10-11-21-22-32-33-43-44-54-5维修费维修费 5 56 68

37、811111818残值残值 4 43 32 21 10 070解：把这个问题化为最短路问题解：把这个问题化为最短路问题用用 表示第表示第i i年初购进一台新设备，虚设一个点年初购进一台新设备，虚设一个点 表示第表示第5 5年底；年底； 用弧用弧 表示第表示第i i年初购的设备一直使用到第年初购的设备一直使用到第j j年年初（第年年初（第j-1j-1年年低）；弧年年低）；弧旁的数字表示第旁的数字表示第i i年初购进设备，一直使用到第年初购进设备，一直使用到第j j年初所需支付的购买年初所需支付的购买、维修的全部费用。、维修的全部费用。 这样设备更新问题就变为：求从这样设备更新问题就变为：求从 到

38、到 的最短路的最短路. .ivijv ,v1v6vijv ,v6v第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 购买费购买费 11111212131314141414机器役龄机器役龄 0-10-11-21-22-32-33-43-44-54-5维修费维修费 5 56 68 811111818残值残值 4 43 32 21 10 071第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 购买费购买费 11111212131314141414机器役龄机器役龄 0-10-11-21-22-32-33-43-44-54-5维修费维修费 5 56

39、 68 811111818残值残值 4 43 32 21 10 0194059121314152130152841292220123456购买购买维修维修残值残值费用费用72 计算结果表明计算结果表明 为最短路，路长为为最短路，路长为4949。即在。即在第第1 1年、第年、第3 3年初各购买一台新设备为最优决策，这时年初各购买一台新设备为最优决策，这时5 5年的总费用年的总费用为为4949。136vvv194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1,28)(v3,40)(v3,49) V1 V2 12V3 19 19V4

40、28 28 28V5 40 40 40 40V6 59 53 49 49 49相邻点相邻点V1 V1 V1 V1 V3V3标号标号73n 图的矩阵表示图的矩阵表示l距离矩阵：设图距离矩阵：设图 ， 为边上的权，表示点为边上的权，表示点 到到 之间的距离，则可构造距离矩阵，之间的距离，则可构造距离矩阵， 其中其中如：以下无向赋权图中的权表示点与点之间距离如：以下无向赋权图中的权表示点与点之间距离G= V,E,ijwijnnA =aijijijw v ,v Ea =0 ijv ,v 其他其他1234512345 v v v v vv09247v9034+A= v 23085v44806v7+560

41、1 12 24 47 76 63 35 54 48 89 92 23 34 45 5或或 对有向赋权图，则定义时将改为。对有向赋权图，则定义时将改为。ijaij v ,v ij (v ,v )ivjv654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v64332256437下图所表示的图可以构造权矩阵B如下:75l邻接矩阵：邻接矩阵：设图设图 ，则邻接矩阵的元素可定，则邻接矩阵的元素可定义如下义如下ijn nA= aij1a=0G= V,Eij v ,v E其他其他对有向赋权图，则定义时将改为对有向

42、赋权图，则定义时将改为如如ijaij v ,v ij (v ,v )1234512345 v v v v vv01010v10110A= v00000v00001v0110012345v5v1v2v3v4v643322564371234561236 6456 010111101100010101111010100101101010 vvvvvvvvvAvvv下图所表示的图可以构造邻接矩阵A如下 关联矩阵：对于图G=(V,E), | V |=n, | E |=m, 有mn阶矩阵M=(mij) mn，其中: 其他其他的一个端点的一个端点是边是边当且仅当当且仅当的两个端点的两个端点是边是边当且仅当当

43、且仅当0ev1ev2jijiijm1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4下

44、图所表示的图可以构造邻接矩阵M如下:M=（mij）=2022-3-23-第6章 图与网络分析-79-SABCDET2524143175572求任意两点间最短距离的矩阵算法2022-3-23-第6章 图与网络分析-80- 构造任意两点间直接到达的最短距离矩阵D（0）= dij（0） S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 构造任意两点间直接到达、或者最多经过1个中间点到达的最短距离矩阵D（1）= dij（1）2022-3-23-第6章 图与网络分析

45、-81-其中 dij（1）= min dir（0）+ drj（0） ， S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=irjdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0）, dSD（0）+ dDE（0） , dSE（0）+ dEE（0）, dST（0）+ dTE

46、（0） =8例如2022-3-23-第6章 图与网络分析-82-其中 dij（2）= min dir（1）+ drj（1） S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=irjdir（1）drj（1）r 构造任意两点间最多可经过3个中间点到达的最短距离矩阵 D（2）= dij（2）2022-3-23-第6章 图与网络分析-83-其中 dij（3）= min dir（2）+

47、 drj（2） S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 构造任意两点间最多可经过7个中间点到达的最短距离矩阵 D（3）= dij（3）2022-3-23-第6章 图与网络分析-84-说明：一般，对于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1） ，k=0，1，2，3， 最多可经过2k-1

48、个中间点： 其数列为 0，1，3，7，15，31， 2k-1， 收敛条件： 当 D（k+1）= D（k）时，计算结束； 设网络中有p个点，即有p-2个中间点，则 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，计算到 k=lg(p-1)/lg2 +1时，收敛，计算结束。2022-3-23-第6章 图与网络分析-85- 例：有7个村镇要联合建立一所小学，已知各村镇小学生的人数大致为S30人， A40人，B20人，C15人，D35人，E25人， T50人。问：学校应建在那一个地点，可使学生总行程最少？ S A B C D E T S 0 2 4 4 8 7

49、 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0L=30 40 20 15 35 25 50人数= 1325 1030 880 1035 910 865 1485T解： 如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。6.5 网络最大流问题2022-3-2387一. 网络最大流的有关概念 1. 有向图与容量网络图中每条边有规定指向的图称为有向图，有向图的边称为弧，记作(vi , vj )，表示方向从点 v

50、i 指向点 vj ，有向图是点与弧的集合，记作 D(V, A )。弧(vi , vj )的最大通过能力，称为该弧的容量，记为c(vi , vj ) ，或简记为 cij 。定义了弧容量的网络称为容量网络。2022-3-2388容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为t)，网络中其余的点称为中间点。从发点到收点之间允许通过的最大流量称为最大流。多个收(发)点的网络可以转换为只含一个收(发)点。2. 流与可行流流是指加在网络各条弧上的一组负载量，对加在弧(vi ,vj )上的负载量记作 f (vi , vj ) ，或简记作 fij ，若网络上所有的 fij =0，这个流称为零流。

51、2022-3-2389以 v( f )表示网络中从 st 的流量，则jtjjjsvvfvvffv),(),()(零流是可行流，求最大流就是求v( f )的最大值。称网络上满足下述条件(1)、(2)的流为可行流：(1) 容量限制条件: 对所有弧有0f (vi , vj ) c (vi , vj )(2) 中间点平衡条件：f (vi , vj ) - f(vj , vi ) =0 (is , t)2022-3-2390二. 割和流量割(集）是指将容量网络中的发点和收点分割开，并使st 的流中断的一组弧的集合（截集）弧旁数字为 cij ( fij ) 有不同的割见教材161页上图中 KK 将网络上的

52、点分割成 V 和 两个集合，并有 sV , t ，称弧的集合 (V, )=(v1 , v3) , (v2 , v4)是一个割。注意，这里不包含(v3 , v2) 。VVV2022-3-2391割的容量是组成它的集合中各弧容量之和，用c(V, )表示，V),(),(),(),(VVjijivvcVVc f (V, ) 表示通过割 (V, ) 中所有 V 方向弧的流量的总和; f ( ,V ) 表示通过割 中所有 V方向弧的流量的总和，则有：VVVVV),(),(),(),(),(),( , ),(),(VVijijVVjijivvfVVfvvfVVf2022-3-2392从 st 的流量等于通过

53、割的从V 的流量减 V的流量，有：VV),(),()(VVfVVffv用 v*( f ) 表示网络中从 st 的最大流，则有),(),()(*VVfVVffvV),(),(),()(*VVcVVfVVffv因此，上例中最大流不会超过14（所有割集中最小者） 。最大流 v*( f ) 应 最小割的容量(用 c*(V, )表示)定理：网络的最大流量等于它的最小割集的容量。定理：网络的最大流量等于它的最小割集的容量。2022-3-23-第6章 图与网络分析-93- 有向图：含有以箭头指示方向的边的网络图。 弧：有向图上的边称为弧。用（vi,vj）表示。 弧的容量：弧上通过负载的最大能力，简称容量。以

54、cij表示。 流：加在网络每条弧上的一组负载量，以fij表示。 可行流：能够通过网络的负载量，通常应满足两个条件： 容量限制条件：对所有的弧，0 fijcij 中间点平衡条件：对任何一个中间点，流入量=流出量 发点、收点、中间点：流的起源点称发点，终到点称收点，其余的点称中间点。 最大流；能够通过网络的最大流量。 割集：一组弧的集合，割断这些弧，能使流中断。简称割。 割的容量：割集中各弧的容量之和。 最小割：所有割集中容量之和为最小的一个割集。2022-3-23-第6章 图与网络分析-94-定理：当网络中不存在任何增广链时，则网络达到最大流状态。二、最大流最小割定理 前向弧+：一条发点到收点链

55、中，由发点指向收点的弧，又称正向弧。 后向弧-：一条发点到收点链中，由收点指向发点的弧，又称逆向弧。 增广链：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即fij0，（反向弧非零流），则称这样的链为增广链。2022-3-23-第6章 图与网络分析-95-三、网络最大流的标号算法(Ford-Fulkerson标号算法)基本思想：寻找增广链，改善流量分布；再重复，直到不 存在任何增广链为止。步骤： 给始点标号：（0，+） 从已标号点i出发，看与其相关联的未标号点j上的弧，对+，若有0fijcij，则可对j点标号，记（i, (j)）， 其中 (j)=min (i) ，cij - fij

56、对-，若有0 fji cij，也可对j点标号，记（ i, (j)）， 其中 (j)=min (i) ，fji （注：若有多个可标号点，可任选其中之一。）若标号中断，则得到最大流状态，否则，重复，继续标号，至收点得到标号，转。2022-3-23-第6章 图与网络分析-96-当收点得到标号，则沿标号得到的增广链进行流量调整： 对+，fij = fij + (t) 对-，fij = fij - (t) 其余弧上的流量不变。 重复上述过程。 最小割集：已标号点集合与未标号点集合相连接的弧中， 流量=容量的弧。97找可行流找可行流给给S 标号标号( S， ) ) t 是否已是否已 标号标号 是否存在已标

57、号是否存在已标号 但未检查的点但未检查的点 倒向追踪倒向追踪找出增广链找出增广链 令调整量令调整量求改进的可行流求改进的可行流+ijij-ijijijijijf +v ,vf = f -v ,vfv ,vt=vlf不存在关于不存在关于的增广链的增广链即为最大流即为最大流 i 已已 标号标号,但未检查但未检查 对对i 进行检查，并对进行检查，并对j 标号标号: 若，且，对若，且，对j 标号标号: ，ijv ,vAijijfcijv , (v )l jiijijv =minv ,c -fll 若，且，对若，且，对j 标号标号: ，jiv ,vAji0fij-v , (v )ljijivminv ,

58、 cll 是是否否2022-3-2398例：用标号法求下述网络图 s t 的最大流量，并找出该网络图的最小割。2022-3-2399解：(1) 先给 s 点标号 (0 , )；2022-3-23100 (2) 从 s 点出发的弧 (s , v2)，因有 fs20 ，且(v1)=min(v2) , f12)=2故对 v1 点标号(v2 , 2)。 (v2 , v4)饱和，不标号。2022-3-23102 (4) 弧 (v1 , v3)，因有 f130 ，且(v4)=min(v3) , f43)=1故对 v4 点标号(v3 , 1)。 (v3 , t)饱和，不标号, v2 已标号。2022-3-2

59、3104(6) 弧 (v4 , t)，因有 f4tc4t ，且(t)=min(v4) , (c4t - f4t)=1故对 t 点标号(v4 , 1)。2022-3-23105(7) 由于收点 t 得到标号，用反追踪法找出网络图上的一条增广链。2022-3-23106(8) 修改增广链上各弧的流量：918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttss非增广链上的所有弧流量不变，这样得到网络图上的一个新的可行流。2022-3-23107重复上述标号过程，由于对点 s 、v1 、v2 、v3 标号后，标号中断，故图中的可行流即为最大

60、流，v*( f )=14已标号点集为V =s , v1 , v2 , v3 ，未标号点集 ，(V , ) =(3 , t) , (2 , 4)为网络的最小割。VV2022-3-23108三. 应用举例例1：P166，例7ADECBF2321211111、方向含义2、E、D之间3、数字含义切断A、F之间的通路，相当于求最小割集。2022-3-23109例2：P167，例81、匹配关系1234562、匹配限制145f=1 f14 f152022-3-23110134f=1 f34 f14 3、等价网络图123456st111111111111例 用标号算法求下图中st的最大流量，并找出最小割。v1