运筹学：第6章图与网络分析

《运筹学：第6章图与网络分析》由会员分享，可在线阅读，更多相关《运筹学：第6章图与网络分析（88页珍藏版）》请在装配图网上搜索。

1、2022-6-291运筹学运筹学OPERATIONS RESEARCH2022-6-292第六章第六章 图与网络分析图与网络分析n图的基本概念与模型图的基本概念与模型 n树图和图的最小部分树树图和图的最小部分树 n最短路问题最短路问题 n网络的最大流网络的最大流n最小费用最大流最小费用最大流 2022-6-293BACD 当地的居民热衷于当地的居民热衷于这样一个问题：这样一个问题：一个漫步者如何能够一个漫步者如何能够走过这七座桥，并且走过这七座桥，并且每座桥只能走过一次，每座桥只能走过一次，最终回到原出发地。最终回到原出发地。尽管试验者很多，尽管试验者很多，但是都没有成功。但是都没有成功。哥尼

2、斯堡的七桥问题哥尼斯堡的七桥问题2022-6-294 为了寻找答案，为了寻找答案，17361736年欧年欧拉把陆地缩为一点，把桥作为拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象连接点的边，将这个问题抽象成图形的一笔画问题。即成图形的一笔画问题。即能否能否从某一点开始不重复地一笔画从某一点开始不重复地一笔画出这个图形，最终回到原点。出这个图形，最终回到原点。欧拉在他的论文中证明了这是欧拉在他的论文中证明了这是不可能的，因为这个图形中每不可能的，因为这个图形中每一个顶点都与奇数条边相连接一个顶点都与奇数条边相连接，不可能将它一笔画出，这就，不可能将它一笔画出，这就是古典图论中的第一个著名问

3、是古典图论中的第一个著名问题。题。ABCDBACD2022-6-295 在实际的生产和生活中，人们为了反映事物之在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样间的关系，常常在纸上用点和线来画出各式各样的示意图。的示意图。例例 有六支球队进行足球比赛，我们分别用点有六支球队进行足球比赛，我们分别用点v v1 1vv6 6 表示这六支球队，它们之间的比赛情况表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知，也可以用图反映出来，已知v v1 1 队战胜队战胜v v2 2 队，队，v v2 2 队战胜队战胜v v3 3队，队，v v3 3 队战胜队战胜v

4、 v5 5 队，如此等等。这队，如此等等。这个胜负情况，可以用下图所示的有向图反映出个胜负情况，可以用下图所示的有向图反映出来。来。2022-6-2961 1 图的基本概念与模型图的基本概念与模型 图（图（graphgraph）是由一些结点或顶点（是由一些结点或顶点（ nodes or nodes or vertices vertices ）以及连接点的边（以及连接点的边（edgesedges）构成。记做构成。记做G G = V,E = V,E ，其中其中 V V 是顶点的集合，是顶点的集合，E E 是边的集合。是边的集合。 给图中的点和边赋以具体的含义和权值，我们称给图中的点和边赋以具体的含

5、义和权值，我们称这样的图为这样的图为网络图网络图（赋权图）（赋权图）1.1 1.1 基本概念基本概念2022-6-297图中的点用图中的点用 v v 表示，边用表示，边用 e e 表示，对每条边可用表示，对每条边可用它所联结的点表示，如图，则有：它所联结的点表示，如图，则有：e1 = v1 , v1，e2 = v1 , v2或或e2= v2 , v12022-6-298 用点和点之间的线所构成的图，反映实际生产和用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。生活中的某些特定对象之间的特定关系。 通常用通常用点点表示研究对象表示研究对象, ,用用点与点之间的线点与

6、点之间的线表示表示研究对象之间的特定关系。研究对象之间的特定关系。 一般情况下，图中点的相对位置如何，点与点之一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，的并不重要，因此，图论中的图与几何图，工程图等图论中的图与几何图，工程图等本质上是不同的。本质上是不同的。2022-6-299端点，关联边，相邻端点，关联边，相邻 若边若边 e e 可表示为可表示为e e = = v vi i , , v vj j ，称称 v vi i 和和 v vj j 是边是边 e e 的的端端点点，同时称边，同时

7、称边 e e 为点为点 v vi i 和和 v vj j 的的关联边关联边，若点，若点 v vi i , , v vj j 与与同一条边关联，称点同一条边关联，称点 v vi i 和和 v vj j 相邻相邻；若边；若边 e ei i 与与 e ej j 有公共端有公共端点，称边点，称边 e ei i 和和 e ej j 相邻相邻. .2022-6-2910 如果边如果边 e e 的两个端点相重，的两个端点相重，称该边为称该边为环环，如果两个点之间，如果两个点之间的边多于一条，称为具有的边多于一条，称为具有多重多重边边，对无环、无多重边的图称，对无环、无多重边的图称为为简单图简单图。环，多重边

8、，简单图环，多重边，简单图2022-6-2911次，奇点，偶点，孤立点次，奇点，偶点，孤立点 与某个点相关联的边与某个点相关联的边的数目，称为该点的的数目，称为该点的次次（或（或度、线度度、线度），记作），记作 d d( (v v) )。次为奇数的点称为次为奇数的点称为奇点奇点，次为偶数的点称为，次为偶数的点称为偶点偶点，次为零的点称为，次为零的点称为孤孤立点。立点。如图：如图： 奇点为奇点为 v v5 5 ， v v3 3偶点为偶点为 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立点为孤立点为 v v6 62022-6-2912链，圈，路，回路，连通图链，

9、圈，路，回路，连通图 图中有些点和边的交替序列图中有些点和边的交替序列 =v v0 0 , , e e1 1 , , v v1 1 , , e e2 2 , , , , e ek k , , v vk k ，若其各边若其各边 e e1 1 , ,e e2 2 , , , , e ek k 各不相同，且任意各不相同，且任意 v vi,ti,t-1-1 , , v vitit (2 (2 t t k k) )都都相邻，称相邻，称 为为链链，如果链中所有的顶点，如果链中所有的顶点 v v0 0 , , v v1 1 , , , , v vk k也不相同，这样的链成为也不相同，这样的链成为路路，起点和

10、，起点和终点重合的链称为终点重合的链称为圈，圈，起点和终点重合的路称为起点和终点重合的路称为回回路路，若在一个图中，每一对顶点之间至少存在一条，若在一个图中，每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则称该图为，否则称该图为不连通不连通的。的。2022-6-291335264734221,vevevevevev链链4734221,vevevev路路,1335264734221vevevevevevev圈圈2022-6-2914完全图完全图 一个简单图中若任意两点之间均有边相连，称这样一个简单图中若任意两点之间均有边相连，称这样的图为的图为完全图。完全图。含有含有

11、 n n 个顶点的完全图，其边数有个顶点的完全图，其边数有 条。条。 2) 1( nn2022-6-2915偶图偶图 如果图的顶点能分成两个互不相交的非空集合如果图的顶点能分成两个互不相交的非空集合 V V1 1 和和V V2 2 , , 使在同一集合中任意两个顶点均不相邻，称使在同一集合中任意两个顶点均不相邻，称这样的图为这样的图为偶图偶图（也称（也称二分图二分图），如果偶图的顶点集），如果偶图的顶点集合合V V1 1 和和V V2 2 之间的每一对顶点都有一条边相连，称这之间的每一对顶点都有一条边相连，称这样的图为样的图为完全偶图完全偶图，完全偶图中，完全偶图中V V1 1 含含m m 个

12、顶点，个顶点，V V2 2 含有含有 n n 个顶点，则其边数共个顶点，则其边数共 m n m n 条。条。2022-6-2916子图，部分图子图，部分图 图图 G G1 1=V V1 1 , , E E1 1 和和 G G2 2=V V2 2 , , E E2 2 ，若有若有 和和 ，称，称 G G1 1 是是 G G2 2 的一个的一个子图子图；若有若有 ，则称，则称 G G1 1 是是 G G2 2 的一个的一个部分图部分图。注意：注意：部分图也是子图，但子图不一定是部分图。部分图也是子图，但子图不一定是部分图。21VV 21EE 2121,EEVV子图：子图：部分图部分图2022-6-

13、29172 2树图和最小部分树树图和最小部分树 树图树图（简称（简称树树，记作，记作 T(V, E)T(V, E)）是无圈的连通图。是无圈的连通图。（无圈，无多重边）（无圈，无多重边）性质性质1.1. 任何树中必存在次为任何树中必存在次为1 1 的点。的点。 次为次为1 1的点称为的点称为悬挂点悬挂点，与之关联的边，与之关联的边 称为称为悬挂边。悬挂边。2.1 2.1 树的性质树的性质2022-6-2918性质性质2.2. 具有具有 n n 个顶点的树恰有（个顶点的树恰有（n n-1-1）条边。条边。性质性质3.3. 任何具有任何具有n n 个点、个点、( (n n - 1)- 1)条边连通图

14、是条边连通图是 树。树。说明：说明：1. 1. 树中只要任意再加树中只要任意再加 一条边，必出现圈。一条边，必出现圈。 2. 2. 树中任意两点之间有且只有树中任意两点之间有且只有 一条通路，从树中任意删掉一条通路，从树中任意删掉 一条边，就不再连通。一条边，就不再连通。 （树是最脆弱的连通图）（树是最脆弱的连通图）2022-6-29192.2 2.2 图的最小部分树图的最小部分树如果如果 G G1 1 是是 G G2 2 的部分图，又是树图，则称的部分图，又是树图，则称 G G1 1 是是 G G2 2 的的部分树部分树（或（或支撑树支撑树）；）；树图的各条边称为树枝树图的各条边称为树枝(

15、(假定各边均有权重假定各边均有权重) )；树枝总长最小的部分树，称为该图的树枝总长最小的部分树，称为该图的最小部分树最小部分树( (也也称称最小支撑树最小支撑树) )。定理定理1.1. 图中任一个点图中任一个点 i i ，若若j j 是与是与i i 相邻点中距相邻点中距离最近的，则边离最近的，则边 i i , ,j j 一定包含在该图的最小部一定包含在该图的最小部分树中。分树中。推论推论. . 把图的所有点分成把图的所有点分成 V V 和和 两个集合，则两个集合，则两集合之间连线的最短边一定包含在最小部分树内。两集合之间连线的最短边一定包含在最小部分树内。V2022-6-29202.3 2.3

16、 避圈法和破圈法避圈法和破圈法寻找最小部分树的方法主要有寻找最小部分树的方法主要有避圈法避圈法和和破圈法破圈法两种。两种。避圈法步骤：避圈法步骤：1.1.从图中任选一点从图中任选一点 v vi i ，让让 v vi i V V ，图中其余点均图中其余点均包含在包含在 中；中；V2. 2. 从从 V V 与与 的连线中找出最小边，这条边一的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为定包含在最小部分树中，不妨设这条边为 v vi i , , v vj j 将其加粗，标记为最小部分树中的边。将其加粗，标记为最小部分树中的边。V3. 3. 令令 ， ；jvV -V4. 4. 重复重

17、复2 2、3 3两步，一直到图中所有点均包含在两步，一直到图中所有点均包含在 V V 中。中。jvVV2022-6-2921避圈法另一种做法避圈法另一种做法： 1.1.在所有各边中找到边权最小的一条，将其作为最小部分树中在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；分树的第二条边；2.2.在剩余的边中，找到边权最小的边，查看其是否与在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加前面的边形成圈，如果没有，则在最小部分树中添加该边

18、，如果形成了圈，则不再考虑该边；该边，如果形成了圈，则不再考虑该边；3.3.重复进行第二步，直到找到第重复进行第二步，直到找到第 n n-1 -1 条边为止。条边为止。（因为有（因为有 n n 个顶点的树中一定有个顶点的树中一定有 n n-1 -1 条边）条边）2022-6-2922例例：分别用两种避圈法构造下图的最小部分树。：分别用两种避圈法构造下图的最小部分树。第一种解法：第一种解法：1. 1. 在点集中任选一点，不妨取在点集中任选一点，不妨取 S S，令令 V V=S S 2. 2. 找到和找到和 S S 相邻的边中，权值最小的相邻的边中，权值最小的 S S , , A A 。2022-

19、6-29233.3.V V=S S , , A A 4. 4. 重复第重复第2 2，3 3步，找到下一个点。步，找到下一个点。2022-6-2924 第二种做法求解过程：第二种做法求解过程：2022-6-2925破圈法求解步骤：破圈法求解步骤：1.1. 从图从图 N N 中任取一回路，去掉这个回路中边中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图权最大的边，得到原图的一个子图 N N1 1。2. 2. 从剩余的子图中任找一回路，同样去掉回路中从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；边权最大的一条边，得一新的子图；3. 3. 重复第重复第 2 2 步

20、，直到图中不再含有回路为止。步，直到图中不再含有回路为止。2022-6-2926用破圈法求解上例：用破圈法求解上例：1. 1. 任意找到一回路，不妨取任意找到一回路，不妨取 DETDDETD，去掉边权最大去掉边权最大的边的边 T T , ,E E ;2. 2. 从剩余的子图中任找一回路，同样去掉回路从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。中边权最大的一条边，得一新的子图；依次类推。2022-6-29272022-6-2928破圈法的另一种解法：破圈法的另一种解法：1.1.从剩余图中找到边权最大一条边，如果将其删除后从剩余图中找到边权最大一条边，如果将其

21、删除后图仍然是连通的，则删除此边，否则不再考虑此边；图仍然是连通的，则删除此边，否则不再考虑此边；2.2.重复上述步骤，直到剩余边数为重复上述步骤，直到剩余边数为 n n-1 -1 为止。为止。2022-6-2929注意：注意：1. 1. 一个图的最小部分树不唯一，该题中用几种解一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；法得到的结果都是相同的，是特殊情况；2.2.不同解法得到的最小部分树所包含的边虽然可不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。

22、总和一定都是相同的，即都达到了最小。2022-6-29303 3最短路问题最短路问题最短路问题最短路问题是指从给定的网络图中找出任意两点之是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。间距离最短（权值和最小）的一条路。某些整数规划和动态规划问题可以归结为求最短路某些整数规划和动态规划问题可以归结为求最短路的问题。如选址问题、管道铺设选线问题、设备更的问题。如选址问题、管道铺设选线问题、设备更新、投资等问题。新、投资等问题。 最短路的求法：最短路的求法：1.1.从某一点至其它各点之间最短距离的狄克斯屈拉从某一点至其它各点之间最短距离的狄克斯屈拉( ( DijkstraDij

23、kstra ) )算法算法; ;2.2.求网络图中任意两点之间的最短距离的矩阵算法。求网络图中任意两点之间的最短距离的矩阵算法。2022-6-2931 3.1 3.1 DijkstraDijkstra 算法算法1.1.设设 d dijij 表示图中两相邻点表示图中两相邻点 i i 与与 j j 的距离，若的距离，若 i i 与与 j j 不相邻，令不相邻，令 d dijij =，显然，显然 d diiii =0=0。 DijkstraDijkstra 算法假设：算法假设：基本思路：基本思路：如果如果 v v1 1 v v2 2 v v3 3 v v4 4 是是 v v1 1 v v4 4 的的

24、最短路径，则最短路径，则 v v1 1 v v2 2 v v3 3 一定是一定是 v v1 1 v v3 3 的最的最短路径。短路径。 v v2 2 v v3 3 v v4 4 一定是一定是 v v2 2 v v4 4 的最短路径。的最短路径。2. 2. 设设 L Lsisi 表示从表示从 s s 点到点到 i i 点的最短距离。点的最短距离。2022-6-2932DijkstraDijkstra 算法步骤：算法步骤：1.1.对起始点对起始点 s s ，因，因 L Lssss =0 =0 ，将，将 0 0 标注在标注在 s s 旁的小旁的小方框内，表示方框内，表示 s s 点已标号；点已标号；

25、2.2.从点从点 s s 出发，找出与出发，找出与 s s 相邻的点中距离最小的一相邻的点中距离最小的一个，设为个，设为 r r ，将将 L Lsrsr = = L Lssss+ + d dsrsr 的值标注在的值标注在 r r 旁的小旁的小方框内，表明点方框内，表明点 r r 也已标号；也已标号；3.3.从已标号的点出发，找出与这些点相邻的所有未标号从已标号的点出发，找出与这些点相邻的所有未标号点点 p p ，若有若有 L Lspsp = =min min L Lssss+ + d dspsp , , L Lsrsr+ + d drprp ，则对，则对 p p 点标号，并将点标号，并将 L

26、Lspsp 的值标注在的值标注在 p p 点旁的小方框内；点旁的小方框内；4.4.重复第重复第 3 3 步，直到步，直到 t t 点得到标号为止。点得到标号为止。求从起始点求从起始点 s s 到终止点到终止点 t t 的最短路径。的最短路径。2022-6-2933例例. . 求下图中从求下图中从 v v1 1 到到 v v7 7 的最短路。的最短路。解解： (1) (1) 从从 v v1 1 点出发，对点出发，对 v v1 1 点标号，将点标号，将 L L1111=0 =0 标注在标注在 旁的小方框内，令旁的小方框内，令 v v1 1V V，其余点其余点属于属于 ；V2022-6-2934L1

27、r = min 0+d12 , 0+ d13 =min5,2=2= L13(2)(2) 同同 v v1 1 相邻的未标号点有相邻的未标号点有v v2 2 、 v v3 3 ，2022-6-2935对对 v v3 3 标号，将标号，将 L L13 13 的值标注在的值标注在v v3 3 旁的小方框内；旁的小方框内；将将( ( v v1 1, , v v3 3) ) 加粗，并令加粗，并令 V Vv v3 3 V V，VvV3。2022-6-2936L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12(3)(3) 同同 v v1

28、 1 , ,v v3 3 相邻的未标号点有相邻的未标号点有v v2 2 、v v4 4 、v v6 6 ，2022-6-2937对对 v v2 2 标号，将标号，将 L L12 12 的值标注在的值标注在 v v2 2 旁的小方框内；旁的小方框内；将将( ( v v1 1, , v v2 2) ) 加粗，并令加粗，并令 V Vv v2 2 V V，VvV22022-6-2938L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16。(4)(4) 同同 v v1 1 , ,v v2 2 , ,v v3

29、 3 相邻的未标号点有相邻的未标号点有v v4 4 、v v5 5、v v6 6 ，2022-6-2939对对 v v6 6 标号，将标号，将 L L16 16 的值标注在的值标注在 v v6 6 旁的小方框内；旁的小方框内；将将( ( v v3 3, , v v6 6) ) 加粗，并令加粗，并令 V Vv v6 6 V V，VvV62022-6-2940L1p = 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)(5)

30、 同同 v v1 1 , ,v v2 2 , ,v v3 3 , ,v v6 6 相邻未标号点有相邻未标号点有v v4 4 、v v5 5、 v v7 7，2022-6-2941对对 v v4 4 , v , v5 5 同时标号，将同时标号，将 L L14 14 = = L L15 15 的值标注在的值标注在 v v4 4, , v v5 5 旁的小方框内；将旁的小方框内；将( ( v v2 2, , v v4 4), ( ), ( v v6 6, , v v5 5) ) 加粗，加粗，并令并令V Vv v4 4v v5 5V V，VvvV54,2022-6-2942L1p = min L15+

31、d57 , L16+d67 =min7+3,6+6=10= L17(6)(6) 同同 v v1 1 , , v v2 2 , ,v v3 3 , , v v4 4, , v v5 5, , v v6 6 相邻的未标号点只相邻的未标号点只有有 v v7 7 ，2022-6-2943 对对 v v7 7 标号，将标号，将 L L17 17 的值标注在的值标注在 v v7 7 旁的小方旁的小方框内；将框内；将( ( v v5 5, , v v7 7) ) 加粗。图中粗线表明从点加粗。图中粗线表明从点 v v1 1 到到网络中其它各点的最短路，各点旁的数字就是点网络中其它各点的最短路，各点旁的数字就是

32、点 v v1 1 到各点的最短距离。到各点的最短距离。2022-6-29443.2 3.2 求任意两点间最短距离的矩阵算法求任意两点间最短距离的矩阵算法用用 DijkstraDijkstra 算法只能计算从图中某一点到其他点算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。出所有各点间的最短距离。例例. . 利用矩阵算法求上述网络图中各点间的最短利用矩阵算法求上述网络图中各点间的最短距离。距离。解解. . 设设 d

33、 dijij 表示图中两相邻点表示图中两相邻点 i i 与与 j j 的距离，的距离，若若 i i 与与 j j 不相邻，令不相邻，令 d dijij =，显然，显然 d diiii =0=0。建立距离矩阵：建立距离矩阵：2022-6-29450636012431067260724702720525077767574737271676665646362615756555453525147464544434241373635343332312726252423222117161514131211ddddddddddddddddddddddddddddddddddddddddddddddddd20

34、22-6-2946从上述距离矩阵可以看出从从上述距离矩阵可以看出从 i i 点到点到 j j 点的直接距点的直接距离，但从离，但从 i i 到到 j j 的最段距离不一定就是从的最段距离不一定就是从 i i 点点直接到直接到 j j 点。点。如上述问题中，从如上述问题中，从 v v1 1 v v2 2 的最短距离应该是的最短距离应该是minmind d1111+ +d d12 12 , , d d1212+ +d d22 22 , , d d1313+ +d d32 32 , , d d1414+ +d d42 42 , , d d1515+ +d d52 52 , , d d1616+ +d

35、 d62 62 , , d d1717+ +d d72 72 即即 minmind d1 1r r+ +d dr r2 2 。因此可以构造一个新的矩阵因此可以构造一个新的矩阵 D D(1)(1) ，令令 D D(1) (1) 中每一中每一个元素为：个元素为： d dijij(1)(1) = =minmind dirir+ +d drjrj ，则矩阵则矩阵 D D(1)(1) 给给出了网络中任意两点之间直接到达及经由一个中间出了网络中任意两点之间直接到达及经由一个中间点时的最短距离点时的最短距离。2022-6-2947再构造矩阵再构造矩阵 D D(2)(2) ， d dijij(2)(2) =

36、=minmind dir ir (1)(1) + +d drjrj (1)(1) 。依次类推构造矩阵依次类推构造矩阵 D D( (k k) ) ， d dijij( (k k) ) = =minmind dir ir ( (k k -1)-1) + +d drjrj ( (k k - -1) 计算停止的控制：计算停止的控制： p p是图中顶点数。是图中顶点数。kpk2lg) 1lg(12022-6-2948该例中该例中 k k = 3= 304381010401244631035712823062710456072104727056127250)1(D043688104012446310355

37、762306278456072845270510677250)2(D)2()3(DD2022-6-2949 上述上述 D D(2)(2) 中的元素给出了各点间的最短距离，中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。需要在计算过程中进行记录。教材教材160页例页例52022-6-29504 4网络的最大流网络的最大流4.1 4.1 网络最大流的有关概念网络最大流的有关概念 1.1.有向图与容量网络有向图与容量网络

38、图中每条边有规定指向的图称为图中每条边有规定指向的图称为有向图有向图，有向图的，有向图的边称为边称为弧弧，记作，记作( (v vi i , , v vj j ) )，表示方向从点表示方向从点 v vi i 指向指向点点 v vj j ，有向图是点与弧的集合，记作，有向图是点与弧的集合，记作 D D( (V V, , A A ) )。弧弧( (v vi i , , v vj j ) )的最大通过能力，称为该的最大通过能力，称为该弧的容量弧的容量，记为记为c c( (v vi i , , v vj j ) ) ，或简记为，或简记为 c cijij 。定义了弧容量的网络称为定义了弧容量的网络称为容量

39、网络容量网络。2022-6-2951容量网络通常规定一个容量网络通常规定一个发点发点( (源点，记为源点，记为s s) )一个一个收收点点( (汇点，记为汇点，记为t t) )，网络中其余的点称为网络中其余的点称为中间点。中间点。从发点到收点之间允许通过的最大流量称为从发点到收点之间允许通过的最大流量称为最大流最大流。多个收多个收( (发发) )点的网络可以转换为只含一个收点的网络可以转换为只含一个收( (发发) )点。点。2. 2. 流与可行流流与可行流流流是指加在网络各条弧上的一组负载量，对加在弧是指加在网络各条弧上的一组负载量，对加在弧( (v vi i , ,v vj j ) )上的负

40、载量记作上的负载量记作 f f ( (v vi i , , v vj j ) ) ，或简记作或简记作 f fijij ，若网络上所有的若网络上所有的 f fijij =0=0，这个流称为，这个流称为零流。零流。2022-6-2952以以 v v( ( f f ) )表示网络中从表示网络中从 s st t 的的流量流量，则，则jtjjjsvvfvvffv),(),()(零流是可行流，求最大流就是求零流是可行流，求最大流就是求v v( ( f f ) )的最大值。的最大值。称网络上满足下述条件称网络上满足下述条件(1)(1)、(2)(2)的流为的流为可行流可行流：(1) (1) 容量限制条件容量限

41、制条件: : 对所有弧有对所有弧有00f f ( (v vi i , ,v vj j ) ) c c ( (v vi i , ,v vj j ) )(2) (2) 中间点平衡条件：中间点平衡条件：f f ( (v vi i , ,v vj j ) ) - - f f( (v vj j , ,v vi i ) ) =0 (=0 (i is s , ,t t) )2022-6-29534.2 4.2 割和流量割和流量割割( (集）集）是指将容量网络中的发点和收点分割开，是指将容量网络中的发点和收点分割开，并使并使s st t 的流中断的一组弧的集合的流中断的一组弧的集合（截集）（截集）弧旁数字为弧

42、旁数字为 c cijij ( ( f fijij ) ) 有不同的割见教材有不同的割见教材上图中上图中 KKKK 将网络上的将网络上的点分割成点分割成 V V 和和 两个两个集合，并有集合，并有 s sV V , , t t ，V称弧的集合称弧的集合( (V V, )=(, )=(v v1 1 , , v v3 3) , () , (v v2 2 , , v v4 4)是一个是一个割割。注意，这里不包含。注意，这里不包含( (v v3 3 , , v v2 2) ) 。VV2022-6-2954割的容量割的容量是组成割的集合中各弧容量之和，用是组成割的集合中各弧容量之和，用c c( (V V,

43、 , ) )表示，表示，V),(),(),(),(VVjijivvcVVc f f ( (V, V, ) ) 表示通过割表示通过割 ( (V V, ) , ) 中所有中所有V V 方向弧的流量的总和方向弧的流量的总和; ; f f ( ( ,V ,V ) ) 表示通过割表示通过割 中所有中所有 V V方向弧的方向弧的流量的总和，则有：流量的总和，则有：VVVVV),(),(),(),(),(),( , ),(),(VVijijVVjijivvfVVfvvfVVf2022-6-2955从从 s st t 的流量的流量等于通过割的从等于通过割的从V V 的流量减的流量减 V V的流量，有：的流量，

44、有：VV),(),()(VVfVVffv用用 v v* *( ( f f ) ) 表示网络中从表示网络中从 s st t 的最大流，则有的最大流，则有),(),()(*VVfVVffvV),(),(),()(*VVcVVfVVffv因此，上例中最大流不会超过因此，上例中最大流不会超过1414（所有割集中最小者（所有割集中最小者) )最大流最大流 v v* *( (f f ) ) 应应 最小割的容量最小割的容量( (用用 c c* *( (V V, ), )表示表示) )2022-6-29564.3 4.3 最大流最小割定理最大流最小割定理增广链：增广链：如果在网络的发点和收点之间能找到一条链，

45、在这条如果在网络的发点和收点之间能找到一条链，在这条链上：链上：所有指向为所有指向为 s st t 的弧（称的弧（称前向弧前向弧，记作，记作+ +），），存存在在f c f f 0(0(非零非零) )，（，（反向弧非零流反向弧非零流）这样的链称这样的链称增广链增广链。2022-6-2957当有增广链存在时，找出当有增广链存在时，找出 0 , , min对对iiiffc再令再令对非增广链上的弧对所有对所有 , , , iiiffff显然，经过计算后显然，经过计算后 f f 仍然为可行流，但较原来仍然为可行流，但较原来的可行流的可行流 f f 流量增大了流量增大了 。因此，只有当网络因此，只有当网

46、络图中找不到增广链时，图中找不到增广链时，s st t 流才不可能进一步增流才不可能进一步增大。大。2022-6-2958定理定理2.2. 在网络中在网络中 s st t 的最大流量等于它的最小的最大流量等于它的最小割集的容量，即割集的容量，即 VVcfv,*证明：证明：略略. .4.4 4.4 求网络最大流的标号算法求网络最大流的标号算法 FordFord- -FulkersonFulkerson 标号算法标号算法，其本质是判断是否存，其本质是判断是否存在增广链，如果存在，则找出增广链，调整流量；在增广链，如果存在，则找出增广链，调整流量；若不存在，则说明已达到最大流。若不存在，则说明已达到

47、最大流。2022-6-2959第一步：首先给发点第一步：首先给发点 s s 标号标号(0 , (0 , ( (s s) ) ) )。第一个数字第一个数字是使这个点得到标号的前一个点的代号，是使这个点得到标号的前一个点的代号，因因 s s 是发点，因此记为是发点，因此记为0 0。第二个数字第二个数字( (s s) ) 表示从上一个标号到这个标号点表示从上一个标号到这个标号点的流量的最大允许调整值，的流量的最大允许调整值，s s 为发点，不限允许调为发点，不限允许调整容量，故整容量，故 ( (s s)=)=。第二步：列出与已标号点相邻的所有未标号点：第二步：列出与已标号点相邻的所有未标号点：202

48、2-6-29602.2. 考虑所有指向标号点考虑所有指向标号点 i i 的弧的弧 ( (h h , ,i i ) ) （即反向（即反向弧弧) ) ，如果有如果有 f fhihi=0=0，对对 h h 不标号，不标号， 若若 f fhihi00，则对则对 h h 点标号，记为点标号，记为( (i , i , ( ( h h ) ) )，其中其中( ( h h ) = min) = min( ( i i ) , ) , f fhihi).). 3.3. 如果某未标号点如果某未标号点 k k 有两个以上相邻的标号点，有两个以上相邻的标号点，可按可按(1) ,(2) (1) ,(2) 中所述规则分别计

49、算出中所述规则分别计算出 ( ( k k ) )的值，并取其中的最大的一个标记。的值，并取其中的最大的一个标记。1.1. 考虑从标号点考虑从标号点 i i 出发的弧出发的弧 ( (i ,j i ,j ) )（即正向弧（即正向弧) )，如果有如果有 f fijij= =c cijij，不给点不给点 j j 标号；若标号；若f fijij c cijij ，则则对对 j j 标号，记为标号，记为( (i , i , ( ( j j ) ) )，其中其中( ( j j ) = ) = minmin( ( i i ) ,() ,(c cijij - -f fijij)2022-6-2961第三步：重复

50、第二步可能出现如下两种结果：第三步：重复第二步可能出现如下两种结果： 1. 1. 标号过程中断，标号过程中断，t t 得不到标号，说明该网络中不得不到标号，说明该网络中不存在增广链，给定流量即为最大流量。记已标号存在增广链，给定流量即为最大流量。记已标号点集为点集为V V，未标号点集为未标号点集为 ，( (V V , ) , ) 为网络为网络的最小割。的最小割。VV2.2. t t 得到标号，这时可用反向追踪法在网络中找到得到标号，这时可用反向追踪法在网络中找到一条从一条从 stst 的有标号点以及相应的弧连接而的有标号点以及相应的弧连接而成的增广链。成的增广链。2022-6-2962第四步：

51、修改流量。第四步：修改流量。设原图中可行流为设原图中可行流为 f f ，令令所有非增广链上的弧对增广链上所有后向弧对增广链上所有前向弧 , , )( , )(ftftff这样得到网络上的一个新的可行流这样得到网络上的一个新的可行流 f f 。第五步：抹掉图上所有标号，重复第一到第四步。第五步：抹掉图上所有标号，重复第一到第四步。注意：注意：在求解步骤中，第三步起到控制运算停止在求解步骤中，第三步起到控制运算停止的作用，而不是第五步。的作用，而不是第五步。2022-6-2963例例：用标号法求下述网络图用标号法求下述网络图 s t 的最大流量，并的最大流量，并找出该网络图的最小割。找出该网络图的

52、最小割。2022-6-2964解解：(1) 先给先给 s 点标号点标号 (0 , )；2022-6-2965 (2) 从从 s 点出发的弧点出发的弧 (s , v2)，因有因有 fs20 ，且且(v1)=min(v2) , f12)=2 故对故对 v1 点标号点标号(v2 , 2)。 (v2 , v4)饱和，不标号。饱和，不标号。2022-6-2967 (4) 弧弧 (v1 , v3)，因有因有 f130 ，且且(v4)=min(v3) , f43)=1 故对故对 v4 点标号点标号(v3 , 1)。 (v3 , t)饱和，不标号饱和，不标号, v2 已标号。已标号。2022-6-2969(6

53、) 弧弧 (v4 , t)，因有因有 f4tc4t ，且且(t)=min(v4) , (c4t - f4t)=1 故对故对 t 点标号点标号(v4 , 1)。2022-6-2970(7) 由于收点由于收点 t 得到标号，用反追踪法找出网络图得到标号，用反追踪法找出网络图 上的一条增广链。上的一条增广链。2022-6-2971(8) 修改增广链上各弧的流量：修改增广链上各弧的流量：918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttss非增广链上的所有弧流量不变，这样得到网络图上非增广链上的所有弧流量不变，这样得到网络图上的一个新的

54、可行流。的一个新的可行流。2022-6-2972重复上述标号过程，由于对点重复上述标号过程，由于对点 s s 、v v1 1 、v v2 2 、v v3 3 标号后，标号后，标号中断，故图中的可行流即为最大流，标号中断，故图中的可行流即为最大流，v v* *( ( f f )=14)=14已标号点集为已标号点集为V V =s s , , v v1 1 , , v v2 2 , , v v3 3 ，未标号点集未标号点集 ，( (V V , ) =(3 , , ) =(3 , t t) , (2 , 4) , (2 , 4)为网络的最小割。为网络的最小割。VV2022-6-29734.5 4.5

55、应用举例应用举例例例1：P166，例，例7ADECBF2321211111 1、方向含义、方向含义2 2、E E、D D之间之间3 3、数字含义、数字含义切断切断A A、F F之间的通路，相当于求最小割集。之间的通路，相当于求最小割集。2022-6-2974例例2：P167，例，例81 1、匹配关系、匹配关系1234562 2、匹配限制、匹配限制145f=1 f14 f152022-6-2975134f=1 f34 f14 3 3、等价网络图、等价网络图123456st1111111111112022-6-29765 5最小费用流最小费用流 在产销平衡问题中，研究的是使费用最小的物资调在产销平

56、衡问题中，研究的是使费用最小的物资调运方案；运方案； 最大流问题中考虑了联结两个点之间的弧的容量限最大流问题中考虑了联结两个点之间的弧的容量限制，但是没考虑流量通过各条弧时发生的费用。制，但是没考虑流量通过各条弧时发生的费用。 实际物资调运中，既要考虑弧的容量又要考虑调实际物资调运中，既要考虑弧的容量又要考虑调运费用的节省，这就是运费用的节省，这就是最小费用流最小费用流要研究的问题。要研究的问题。 即要寻求一个最大流即要寻求一个最大流 f f，使得总的运输费用，使得总的运输费用 b(fb(f) ) 最小。最小。ijijfbfb)(min2022-6-2977寻求最大流寻求最大流 f f 的方法

57、：的方法：从某可行流出发寻找增广链，从某可行流出发寻找增广链，然后沿着该链调整流量，直至达到最大流量。然后沿着该链调整流量，直至达到最大流量。附加附加”费用费用”的因素：的因素：希望沿增广链增加流量后，希望沿增广链增加流量后，增加的费用是最小的。增加的费用是最小的。这样在前一个最小费用流的基础上（这样在前一个最小费用流的基础上（ ）调整流量后，新的流量下的费用也是最小的。调整流量后，新的流量下的费用也是最小的。)(),(kkfbfv如何做到如何做到沿增广链增加流量后，增加的费用最小沿增广链增加流量后，增加的费用最小？ 假设假设 是流是流 f f 的一条增广链，沿此增广链调的一条增广链，沿此增广

58、链调整整 1 1 个单位流量，引起的费用增加量如下：个单位流量，引起的费用增加量如下： 2022-6-2978ijijijijijijijijbbffbffbfbfbfb)()()()()(寻找寻找费用增加最小的增广链费用增加最小的增广链就相当于：在由就相当于：在由 b bijij 作作为弧权的为弧权的有向图有向图中寻找从发点到收点的最短路。中寻找从发点到收点的最短路。 （增广链的费用）（增广链的费用）2022-6-2979寻找最小费用最大流的步骤：寻找最小费用最大流的步骤： 1 1、从零流、从零流f f0 0 开始，其费用就是最小。开始，其费用就是最小。2 2、寻找费用最小的增广链：对上一个

59、可行流、寻找费用最小的增广链：对上一个可行流 f fk k 构造赋权有向图构造赋权有向图W(fW(fk k),),，每对结点间有正向和反向，每对结点间有正向和反向弧。方法如下：弧。方法如下：ijijijijijijcfcfbw正向弧正向弧反向弧反向弧00jijijijiffbw在此图中找到从发点到收点的最短路。在此图中找到从发点到收点的最短路。2022-6-29803 3、沿此最短路（费用最小的增广链）调整流量，调、沿此最短路（费用最小的增广链）调整流量，调整量为整量为: :得到新的可行流得到新的可行流 f fk+1 k+1 。4 4、重复上述、重复上述2 2、3 3步，直至不存在从发点到收点

60、的最步，直至不存在从发点到收点的最短路。短路。( (即不再存在增广链）即不再存在增广链）0 , , min对对ijijijffc2022-6-2981 例：例：如图，图中弧旁数字如图，图中弧旁数字( (c cijij , , b bijij) )中，中，c cijij 表示弧表示弧容量，容量， b bijij 表示单位费用，求从表示单位费用，求从 s s t t 的最小费用的最小费用的最大流。的最大流。2022-6-2982解：解：1. 1. 先不考虑弧容量，寻找最短路：先不考虑弧容量，寻找最短路：该图中路径旁数字该图中路径旁数字为单位费用。为单位费用。2. 2. 根据各弧容量，将路径上的流量

61、调整到最大可根据各弧容量，将路径上的流量调整到最大可 能：能：2022-6-29833. 3. 构建新的网络图：构建新的网络图：(1)(1)对于非饱和且非零的弧对于非饱和且非零的弧( (i i , , j j) ) ，在两点间分在两点间分 别给出弧别给出弧( (i i , ,j j) ) 和和( ( j ,ij ,i) , ) , 其权值其权值分别为分别为 b bijij 和和 - - b bijij； ( (2) 2) 对于饱和弧对于饱和弧( (i i, ,j j) ) ，只画出只画出弧弧( (j,ij,i) ) ，其权值其权值 为为 - -b bijij；(3) (3) 对于零弧对于零弧(

62、 (i i, ,j j) ) ，只给出弧只给出弧( (i i, ,j j), ), 其权其权值为值为 b bijij 。2022-6-29844. 4. 重复第重复第 1 1 步，构造最短路步，构造最短路( (即费用最小增广链即费用最小增广链) )：5. 5. 重复第重复第 2 2 步，在原流量不减少的前提下调整流步，在原流量不减少的前提下调整流量；量；2022-6-2985 6.6.重复第重复第 3 3 步，重新构造网络图，原则与第步，重新构造网络图，原则与第 3 3 步步 相同：相同：7. 7. 重复第重复第 4 4 步，步， 寻找最短路：寻找最短路：2022-6-29868.8.重复第重复第 5 5 步，在原流量不减少的前提下调整流步，在原流量不减少的前提下调整流 量；量；9.9.重复第重复第 6 6 步，重新构造步，重新构造 网络图，原则与第网络图，原则与第 3 3 步步 相同：相同：2022-6-298710. 10. 重复第重复第 7 7 步，构造最短路：步，构造最短路：11.11.重复第重复第 8 8 步；步；2022-6-298812.12.重复第重复第 9 9 步，重新构造网络图：步，重新构造网络图：13.13.由于无法再找到最短路，因此计算停止，第由于无法再找到最短路，因此计算停止，第 11 11步所得流量即为最小费用的最大流。步所得流量即为最小费用的最大流。