网络最大流

格式：ppt
大小：669.50 KB
文档页数：30

下载文档原格式

/ 30

最大流常见算法

最大流常见算法最大流问题是图论中的一个重要问题，其求解方法有多种，本文将介绍最常见的几种算法。

一、最大流问题简介最大流问题是在一个网络中寻找从源点到汇点的最大流量的问题。

网络是由一些节点和连接这些节点的边构成的，每条边都有一个容量，表示该边所能承载的最大流量。

源点是流量的起点，汇点是流量的终点。

在网络中，还可能存在其他节点和边。

二、Ford-Fulkerson算法Ford-Fulkerson算法是最早用于解决最大流问题的算法之一。

该算法基于增广路径来不断增加流量，直到无法再找到增广路径为止。

1. 算法步骤（1）初始化：将所有边上的流量设为0。

（2）寻找增广路径：从源点开始进行深度优先或广度优先搜索，在搜索过程中只选择剩余容量不为0且没有被标记过的边，并记录路径上容量最小值min。

（3）更新路径上各个边上的流量：将路径上各个边上的流量加上min。

（4）返回第二步，直到无法找到增广路径为止。

2. 算法分析Ford-Fulkerson算法可以保证在有限步内求解出最大流，但是其时间复杂度与增广路径的选择有关，最坏情况下可能需要指数级的时间复杂度。

三、Edmonds-Karp算法Edmonds-Karp算法是基于Ford-Fulkerson算法的一种改进算法。

该算法使用BFS来寻找增广路径，可以保证在多项式时间内求解出最大流。

1. 算法步骤（1）初始化：将所有边上的流量设为0。

（2）寻找增广路径：从源点开始进行BFS，在搜索过程中只选择剩余容量不为0且没有被标记过的边，并记录路径上容量最小值min。

（3）更新路径上各个边上的流量：将路径上各个边上的流量加上min。

（4）返回第二步，直到无法找到增广路径为止。

2. 算法分析Edmonds-Karp算法相对于Ford-Fulkerson算法来说，在同样的网络中，其时间复杂度更低，可以保证在O(VE^2)的时间内求解出最大流。

但是在某些特殊情况下仍然可能需要指数级时间复杂度。

最大流的概念

最大流的概念最大流（Maximum Flow）是指在一个有向图中，给每条边一个容量限制，然后寻找一条从源点到汇点的路径，使得路径上的每条边的流量都不超过其容量限制的最大值。

最大流问题是网络流理论中的一种经典问题，具有广泛的应用领域，如网络优化、流量分配、资源调度等。

最大流问题可以用图论中的图来进行模型表示，其中图中的节点表示流经的位置，边表示流量通路，每条边还有一个容量值，表示该边所能承载的最大流量。

图中通常包括一个源点（Source）和一个汇点（Sink），各个节点与源点和汇点之间的连接关系构成了一个流量网络。

每个节点上的流量是指通过该节点的流量总和，而边上的流量是指该边上的实际流量。

最大流问题的求解可以采用不同的算法，其中最常见的是Ford-Fulkerson算法和Edmonds-Karp算法。

下面将对这两种算法进行详细介绍。

1. Ford-Fulkerson算法Ford-Fulkerson算法是最大流问题的经典算法，它的思想是不断寻找增广路径，并通过增加该路径上各边的流量来增加整个流量网络的流量。

算法的基本步骤如下：(1) 初始化流量网络的流量为0。

(2) 通过任意的路径查找算法（如深度优先搜索）找到一条从源点到汇点的增广路径。

(3) 在该增广路径上增加流量的值为该路径上残余容量的最小值。

(4) 更新整个流量网络中各边的残余容量和反向边的流量。

(5) 重复步骤2至4，直到无法找到增广路径为止。

2. Edmonds-Karp算法Edmonds-Karp算法是Ford-Fulkerson算法的一种改进，它通过使用广度优先搜索来寻找增广路径，使得算法的时间复杂度优于Ford-Fulkerson算法。

算法的具体步骤如下：(1) 初始化流量网络的流量为0。

(2) 通过广度优先搜索查找一条从源点到汇点的最短增广路径。

(3) 在该增广路径上增加流量的值为该路径上残余容量的最小值。

(4) 更新整个流量网络中各边的残余容量和反向边的流量。

网络流基础-最大流最小割定理

⽹络流基础-最⼤流最⼩割定理
最⼤流最⼩割定理，指⽹络流的最⼤流等于其最⼩割。

最⼤流指符合三个性质的前提下，从S到T能流过的最⼤流量。

最⼩割指符合割的定义，最⼩的割容量。

求最⼤流：
不断寻找增⼴路，计算能增加的最⼩流量，然后增加。

找到⼀条增光路，最多能流过2，则：
找到第⼆条路径：
最后还剩a-c-e⼀条，则可计算出最⼤流量为4。

但遇到以下情况，且第⼀条路径为a-b-c-d时，就不⾏了：
此时需要增加反向路径，即当减去增⼴路时，反向加上减去的流量，提供后悔的选择：
这样，当考虑a-c-b-d时，可以对冲掉b-c的流量。

证明：
定理⼀：对于任⼀割和任⼀流，流量等于正向割边流量减去反向割边流量。

即f = f c+ - f c-，其中c+代表正向割边流量。

推论：任⼀割容量必定⼤于等于任⼀流量，由于：C+ > f c+ > f c+ - f c- > f。

则如果存在某流量和某割，则此流量必定为最⼤流，此割必定为最⼩割。

当我们计算出最⼤流时，不妨思考下此时的残留⽹络：
此时残留⽹络不存在增⼴路，即不存在⼀条能从S到T的路径。

此时残留⽹络中，我们把S能到达的节点记为s'集，能到达T的节点记为t’集，则s'和t'构成割集。

在残留⽹络中，流量指容量为0的边（满流），⽽这些边⼜是割边，所以流量和等于割的容量和。

⽐如对于：
其⼀个残留⽹络为：
其中两条虚线边为满流的边，也是割边。

网络流——求网络最大流

4 1 4 8
4 2 2 6
7
9
(1,4) V2 (0,+∞) V1
(2,4) V4 (4,4) V6
(1,8)
V3
V5 (2,1)
4 1 4 8
4 2 2 6
7
9
(-4,2) V2 (0,+∞) V1 4 4
(3,2) V4 4
(4,2) V6
(1,8)
V3
V5 (3,2)
4 1 4 8
4 2 2 6
7
9
(5,2) V2 (0,+∞) V1 2 4 4 V4 6
(5,2) V6
2
(1,6)
V3
V5 (3,2)
4 1 4 8
4 2 2 6
7
9
V2 (0,+∞) V1 4 4
4
V4
6 V6 2
2 2
(1,4)
V3
V5
存储结构
const maxn=100; type nodetype=record{可改进路顶点类型可改进路顶点类型} 可改进路顶点类型 l,p:integer;{标号、检查标志标号、标号检查标志} end; arctype=record{网顶点类型网顶点类型} 网顶点类型 c,f:integer;{容量、流量容量、容量流量} end; gtype=array[0..maxn,0..maxn] of arctype; ltype=array[0..maxn] of nodetype; var lt:ltype; g:gtype; n,s,t:integer;{顶点数、源点、汇点顶点数、顶点数源点、汇点} f:text;
增广后的F

网络流最大流算法

• 复杂度：在一定基础上可达O(mn log n)，其中，n为点数、mple
• Dinic算法的Example
Fujishige algorithm
• 传说中的弱多项式算法
– 对简单有向图G以及整容量可在O(mnlog u max ) 时间内正确求解最大流问题，其中n为点数、 m为边数、u max为最大边容量（详见课本153）
– 2、活动点(active)：除s、t外，流入>流出的点（即超出量>0的点）
Push–relabel maximum flow algorithm （推流-重标算法）
• Definition：
– 3、距离标号(distance labels, or heights):
• a、h(s)=n,h(t)=0；（s和t的标号是固定的） • b、剩余图中的所有边(u,v)，有h(u)<=h(v)+1；
Dinic's algorithm
• Definition：
– 阻塞流(blocking flow)：
• 网络(G,u,s,t)对应的分层图中所有可扩路的并，即为阻塞流
Dinic's algorithm
• 算法步骤：
– 1、令所有边的流量f=0； – 2、构造剩余图的分层图(level graph) – 3、在分层图中求一个阻塞的s-t流(the blocking flow)f'，若f'=0，则止 – 4、用f'对f扩充，转2
Theorem
• 网络N(G,u,s,t)中的可行流f是N的最大流当且仅当N中不存在f可扩路
– 必要性：若有可扩路P，沿P使f扩大即可 – 充分性：设网络中不存在可扩路
• 令S = {v∈V(G)|从源s到v有f可扩路}∪{s}，则与最大流最小割定理同样可证K' = (S,T)是网络中的一个割，且value(f) = cap(K') • 设F为最大流，K为最小割，则value(f) <= value(F) <= cap(K) <= cap(K') • 故f即为最大流，K'即为最小割

数学网络分析最短路和最大流问题

得到网络上一个新的可行流f’。
(5) 擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。
网络的最大流
例6.10 用标号算法求下图中s→t的最大流量，并找出最小割。
v1 8(7)
5(4)
s
9(3) 2(0)
v3 5(4)
6(1)
t●
7(5) v2
10(8)
9(9)
v4
网络的最大流
8 ⑥ 16 24
⑧ 18
2
13 3
6
2
④
8 10
2
6 12
⑦
6
18 24
所有点都已标号，点上的标号就是v1到该点的最短距离，最短
路线就是红色的链。
最短距离的矩阵算法
网络图的矩阵表示
v1 d11 d1i d1n
v2
d
21
B
vi
d
i1
d 2i
d ii
d
2
n
d in
dij表示i点到j点两相邻点间的距离，若i和j点不相邻，则
从s点出发，找出与s点相邻的所有的点，记为点集V1，取vr， s.t.， L sr=mvii V n 1{sL s+ ，ds则} i 将r点标注，并将Lsr的值标注在 r点旁的小方框内。
从已标注的点出发，找出与这些点相邻的所有未标注的点记为点集V2，取vt ，s.t.，L s= t m v i V i 2 { n sL + sd s;i L s+ rd r} i ，则将t点标注，并将Lst的值标注在t点旁的小方框内。
f ( v i,v j) f ( v j,v i) 0 ( i s ,t )

16.网络最大流问题

l(vj)=min[l(vi),cij-fij],
l(vj)=min[l(vi),fji]
重复上述步骤，一旦vt被标号，则得到一条vs到vt的增广链。若所有标号都已检查过，而vt尚未标号，结束，这时可行流，即最大流。（二）调整过程
从vt 开始，反向追踪，找出增广链 µ ，并在µ 上进行流量调整。（1）找增广链如vt 的第一个标号为k（或-k），则弧（vk，vt） ∈µ（或弧（vt，vk) ∈µ)。检查vk 的第一个标号，若为i （或-i），则(vi,vk) ∈µ (或(vk,vi) ∈µ )。再检查vi 的第一个标号,依此下去,直到vs 。被找出的弧构成了增广链 µ 。
5. 增广链对可行流 f ={ fij }：非饱和弧：fij < cij 非零流弧：fij >0 饱和弧：fij =cij 零流弧：fij =0
链的方向：若µ 是联结vs和vt的一条链，定义链的方向是从vs到vt 。 v2 v4 5.2
10.5 3.2 4.1 5.1 3.3 11.6
v1
8.3
已检查标号点网络中的点未检查未标号点
标号：（前点标记，前点到该点的弧流量可调整量）开始，vs 标上（0，∞），vs 是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点vi ，对一切未标号的点vj 。（1）若弧（vi，vj）上，fij<cij，则给vj 标号(vi ，l(vj))， l(vj)=min[l (vi), cij-fij], vj 成为标号而未检查的点。（2）若弧（vj，vi）上，fji>0，则给vj 标号(- vi, l (vj))， l (vj)=min[l (vi), fji], vj 成为标号而未检查的点。 vj vj (i , l(vj)) vi (-i , l(vj)) vi fij<cij f ji>0

最大流问题标号法例题详解

最大流问题标号法例题详解最大流问题标号法例题详解本文以一道标号法求解最大流问题的例题胶加以详细讲解，帮助读者了解其原理及运算步骤。

题目如下：给定一个网络结构如下：s (源点) 0----1----2----3----4---- t (汇点)a 25 10 12 15 20其中 s 是源点，t是汇点，aij（i,j=0,1,2,3,4)是每条弧的容量，求整个网络的最大流量。

解：1、设置标号：在最大流问题中，为了求解最大流，最常用的方法是标号法。

首先，要设置各结点标号，因为本题中有5个结点，s源点的标号为0，t汇点标号为4，其他结点即1，2，3依次标号，标号的设定不仅便于求解，而且可以在初始化的时候使用。

2、初始化标号：初始化标号即将各结点初始化为两个空集合{}，即各结点的访问和未访问标号都是空集合，即无访问的结点标号为{}，访问过的结点标号也为{}。

3、依据标号法，从源点(s=0)计算，得出每条弧的剩余容量Cij，具体推导如下：源点0 1 2 3 41 0 25 10 12 152 0 0 10 7 103 0 0 0 8 104 0 0 0 0 20其中：Cij=aij-fij (i,j=0,1,2,3,4)其中，aij 为每条弧的容量，fij 为每条弧的流量，在初始情况下，fij=0，故Cij=aij。

4、找增广路径：从源点s开始，用深度优先搜索法查找从s到t的增广路径，具体步骤如下：设置一个数组P[i]用以记录路径，P[i]表示从s到i节点所经过的上一个结点，先从源点s开始，P[0]=-1，然后查找s出发可以到达的结点，若Cij>0，则有路可达，将P[j]=i（j为s出发可达的结点），接着查找j出发可以到达的结点（该结点未被访问过）若Cjk>0，则有路可达，把P[k]=j，以此类推，直到找到P[t]=-1，即从s到t 的一条增广路径找到，这条增广路径的路径上的容量称为Cmin，它是该增广路径上各结点之间的容量最小值。

最大流算法的实施步骤

最大流算法的实施步骤1. 算法介绍最大流算法是解决网络流问题的一种常用算法。

给定一个网络图，其中包含源点s和汇点t，以及带有容量限制的边。

最大流算法的目标是找到从源点s到汇点t的最大流量。

2. 算法步骤最大流算法通常采用增广路径的方法来逐步增加网络的流量，直至无法再找到增广路径为止。

下面是最大流算法的具体步骤：步骤 1：初始化1.创建一个残余网络图，用于记录每条边的剩余容量。

2.初始化所有边的流量为0。

步骤 2：寻找增广路径1.在残余网络图中使用广度优先搜索（BFS）或深度优先搜索（DFS）寻找从源点s到汇点t的增广路径。

2.如果找到增广路径，则记录该路径上的最小剩余容量（即该路径上的最小容量）。

步骤 3：更新流量1.将步骤2中找到的路径上的最小剩余容量，加到该路径上的每条边的流量中。

2.同时更新残余网络图中该路径上每条边的剩余容量。

步骤 4：重复步骤2和31.重复步骤2和3，直到无法再找到增广路径。

2.此时，经过网络的流量即为最大流量。

3. 算法的示例假设有以下网络图作为示例：s ---4---> 1 ---2---> 3 --3--> t| / \\ / |5 / \\ / 6| / \\ / |v v v v v2 1 43 14 / v| 2| / v |2 2 | 2| t |+-------- 5-----+------------+按照上述步骤，我们来计算最大流量：1.初始化残余网络图和边的流量。

s ---4/0---> 1 ---2/0---> 3 --3/0--> t| / \\ / |5/0 / \\ / 6/0| / \\ / |v v v v v2/0 1/0 4/0 3/0 1/0| / \\ | |4/0 / v | 2/0| / v |2/0 t |+-------- 5/0 -----+------------+2.使用BFS寻找增广路径：s -> 1 -> 3 -> t，最小剩余容量为2。

求解最大流问题的算法和模型

求解最大流问题的算法和模型最大流问题是图论中的一个基本问题，涉及到网络流的计算和优化。

在实际应用中，最大流问题的求解涉及到诸多算法和模型，如增广路径算法、Ford-Fulkerson算法、Dinic算法、最小割定理等。

本文将从这些方面进行论述。

1. 增广路径算法增广路径算法是求解最大流问题的经典算法，其基本思想是不断地寻找增广路径，通过增加路径上的流量来增加整个网络的流量。

具体来说，首先通过深度优先搜索或广度优先搜索找到一条从源点到汇点的增广路径，然后确定路径上的最小流量d，将当前流量增加d，将反向边的流量减少d，同时计算当前网络的流量。

2. Ford-Fulkerson算法Ford-Fulkerson算法是一种经典的增广路径算法，其基本理念与增广路径算法相同，但采用不同的策略来确定增广路径。

具体来说，Ford-Fulkerson算法采用贪心策略，在每次迭代中选择路径上的最小容量，从而确定增加的流量。

此外，Ford-Fulkerson算法还引入了残量图的概念，用于计算增广路径的容量。

3. Dinic算法Dinic算法是一种高效的增广路径算法，其主要优点是采用了分层图的策略来确定增广路径，使得每次迭代的搜索范围大为缩小。

具体来说，Dinic算法首先利用BFS算法确定每个节点的分层，然后在分层图上通过DFS算法查找增广路径，在路径上增加流量，更新分层图，重复此过程直至求解最大流。

4. 最小割定理最小割定理是求解最大流问题的重要定理，其核心思想是将网络分成两个不相交部分，并将其最小的割称为最小割。

最小割定理指出，在任意网络中，最大流等于最小割。

因此，求解最大流可以转化为求最小割问题，即在网络中寻找一组最小割，使得所有的割中容量最小的一组割。

总之，求解最大流问题是图论中的一个重要问题，其求解涉及到诸多算法和模型，如增广路径算法、Ford-Fulkerson算法、Dinic 算法、最小割定理等。

在实际应用中，不同情况下可能需要采用不同的算法和模型来求解，需要灵活应用。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

容量为20 容量为
• 最小截集： • 容量最小截集的称为网络G的最小截集。 • 最大流-最小截集定理： • 在任一个网络D中，从vs到vt的最大流的流量等于分离的最小截集的容量。
（二）、求最大流的标号法
标号过程： 1．给发点vs 标号（0，+∞）。 2．取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边 (v j , vi ) ∈ E ，且 f j i > 0 ，那么给vj 标号 (−vi , δ j ) ，其中： δ j = min( f j i , δ i ) （2）如果边 (vi , v j ) ∈ E ，且 f ij < cij，那么给vj 标号 ( +vi , δ δ j = min(ci j − f i j , δ i ) ，其中：j ) 3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。
2．去掉所有标号，回到第一步，对可行流重新标号。
求下图所示网络中的最大流，弧旁数为
v2 (3 , 3) vs (5 , 1) (1 , 1) v1 （-v1, 1）） v2 (3 , 3) （0，+∞），） vs (5 , 1) v1 （+ vs , 4）） (2 , 2) (1 ,1) (1 , 1) (3 ,0) (2 ,1) v3 （-v2 ，1）） (2 , 2) (4 ,3) (1 ,1) (3 ,0) (2 ,1) v3 （+v2，1）） v4 (5 ,3) v4 (5 ,3) vt
f = f (v i , v j ) = { f i j }
{
}
其中f(v 叫做弧(v 上的流量其中 i ,vj) =fij 叫做弧 i，vj)上的流量。上的流量。
2、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi ,vj）∈E 有 0 δ fij δ cij 。（2）平衡条件：对于发点vs，有 ∑ f − ∑ f = W
+ −
0 ≤ f i j < ci j 0 < f i j ≤ ci j
(v i , v j ) ∈ µ + (v i , v j ) ∈ µ −
µ + 中的每一条弧都是非饱和弧即 µ − 中的每一条弧都是非零流弧即
则称 µ 为从vs到vt 的关于f 的一条可增广链。推论可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。
可行流中 fij＝cij 的弧叫做饱和弧，fij＜ cij的弧叫做非饱和弧。fij＞0 的弧为非零流弧，fij＝0 的弧叫做零流弧。
3、容量网络G，若 µ 为网络中从vs到vt的一条链，给 µ 定向为从vs到vt，µ 上的弧,凡与 µ 方向相同的称为前向弧前向弧，凡与 µ 方向相反的前向弧称为后向弧后向弧，其集合分别用 µ 和 µ 表示。后向弧 f 是一个可行流，如果满足：
容量为24 容量为
而 ( v 3 , v 2 ) 和 ( v 4 , v 5 )3 (5) 6(3) 4 (1) 5 (2) 9 (3) 5 (2)
v5
4 (2) 4 (1) 5 (0)
9 (5)
v1
v4
v7
10 (1)
v3
v6
V 设 V1′ = {v1 , v 2 } ， 2′ = {v 3 , v4 , v5 , v 6 , v7 } 则截集为 (V1′,V2′) = {(v1v 3 ), (v 2 , v4 ), (v 2 , v5 )}
得到新可行流f (k) 。对f (k)重复上面步骤，返回（2）。例8.11 求网络的最小费用最大流，弧旁权是（bij , cij）
v1 (4 ,8) (2 ,3) vs (1 ,4) v2 (3 ,2) (6 ,7) vt (1 ,6) v3 (2 ,5)
v1 (4 ,8) (2 ,3) vs (1 ,4)
四、最大流问题（一）、基本概念
1、设一个赋权有向图D=（V, E）,在V中指定一个发点、设一个赋权有向图在中指定一个发点 vs和一个收点 t ,其它的点叫做中间点。对于中的每一个和一个收点v 其它的点叫做中间点对于D中的每一个其它的点叫做中间点。都有一个非负数c 叫做弧的容量。弧（vi , vj）∈E ,都有一个非负数 ij,叫做弧的容量。我们都有一个非负数叫做弧的容量把这样的图D叫做一个容量网络简称网络叫做一个容量网络，网络，把这样的图叫做一个容量网络，简称网络，记做 D=（V，E，C）。）（网络D上的流是指定义在弧集合E上的一个函数上的流，网络上的流，是指定义在弧集合上的一个函数
( v s , v j )∈E sj ( v j , v s )∈E js
对于收点vt ，有 ∑
( v t , v j )∈E
ft j −
( v j , v t )∈E
∑f
jt
= −W
对于中间点，有 ∑ f − ∑ f = 0 W为网络流的总流量。可行流总是存在的，例如f={0}就是流量为0 的可行流。最大流问题就是在流量网络中，寻找流量最大的可行流。
µ + = {(v1 , v 2 ), (v 3 , v 6 ), (v 6 , v 7 )} µ − = {(v 3 , v 2 )}
µ
是一个增广链
显然图中增广链不止一条
4、容量网络D =（V，E，C），vs为始点， vt为终点。如果把V分成两个非空集合 S , S 使 v ∈ S , v ∈ S ，则所有始点属于，而终所有始点属于S，所有始点属于的弧的集合，点属于 S 的弧的集合，称为由S决定的截集, 记作 ( S , S )。截集 ( S , S ) 中所有弧的容量之和，称为这个截集的容量，记为 C ( S , S ) 。
7 vs 3 S
v1 4
5 5 6
v3 7 3 8 v4 vt
v2
5 (3)
v2
13 (5) 6(3) 4 (1) 5 (2) 9 (3) 5 (2)
v5
4 (2) 4 (1) 5 (0)
9 (5)
v1
v4
v7
10 (1)
v3
v6
V 设 V1 = {v1 , v 2 , v5 } ， 2 = {v 3 , v4 , v 6 , v7 } 则截集为 (V1 ,V2 ) = {(v1v 3 ), (v 2 , v4 ), (v5 , v 7 )}
调整过程按点的第一个标号寻找一条增广链对vt,,按逆方向进行调整，下式中的 δ 为δ t
fi j + δ 1．令 f i′j = f i j − δ fi j (v i , v j ) ∈ µ + (v i , v j ) ∈ µ − (v i , v j ) ∉ µ
70（70）（）
v1
50（50）（） 50（20）（）
vt1 ∞ （150 ） v t
∞ （200 ）
v s1
70（50）（） ∞ （120 ） 130（100）（）
（） v2 150（150） 100（100）（）
vt 2
vs
∞ （230 ） vs 2 150（130）（）
(c i j , f i j )
(4 ,3)
(+ v ，1) vt 3
v2 (3 , 3) vs (5 , 2) (1 , 0) v1 v2 (3 , 3) （0，+∞），） vs (5 , 2) (1 , 0) v1 （+ vs , 3））
(4 ,3) (1 ,0)
v4 (5 ,3) (3 ,0) (2 ,2) vt
u+
寻找关于f 的最小费用增广链：构造一个关于f 的赋权有向图L(f ) ，其顶点是原网络G的顶点，而将G中的每一条弧 ( vi, vj )变成两个相反方向的弧（vi， vj）和(vj , vi)，并且定义图中弧的权lij为： 1.当 (vi , v j ) ∈ E ，令 d i j 当 f i j < c i j
li j = + ∞ 当 f i j = ci j
2.当（vj，vi）为原来网络G中（vi， vj）的反向弧，令 − d i j 当 f i j > 0
l ji = + ∞ 当 fi j = 0
在网络G中寻找关于f 的最小费用增广链等价于在L(f )中寻求从vs 到vt 的最短路。
5 (3)
v2
13 (5) 6(3) 4 (1) 5 (2) 9 (3) 5 (2)
v5
4 (2) 4 (1) 5 (0)
9 (5)
v1
v4
v7
10 (1)
v3
v6
µ = {v1 , (v1 , v 2 ), v 2 , (v 3 , v 2 ), v 3 , (v 3 , v 6 ), v 6 , (v 6 , v 7 ), v 7 }
s t
S = ( v s , v 2 ) S = ( v1 , v 3 , v 4 , v t ) ( S , S ) = {(v s , v1 ) , (v 2 , v4 ) , (v 2 , v 3 )} C ( S , S ) = l s1 + l 24 + l 23 = 7 + 6 + 5 = 18
4 (2) 4 (1) 5 (0)
9 (5)
v1
v4
v7
10 (1)
v3
v6
截集1 截集1
v2
13 (11) 6(6) 4 (0) 5 (5) 9 (9)