饱和弧——如果容量网络D中某弧(vi,vj)上的流量fij等于其容量限制cij，即fij?cij，则称(vi,vj)为D的饱和弧。

前向弧、后向弧——假设Q为容量网络D中从vS到vT的链，并且规定vS和

vT为链的方向，链上与链的方向一致的弧称为前向弧，与链的方向相反的弧称

为后向弧。前向弧集合用Q?表示，后向弧集合用Q?表示。

可增广链——假设f是容量网络D的一个可行流，如果满足

??0?fij?cij???0?fij?cij(vi,vj)?Q?

(vi,vj)?Q?则称Q为从vS到vT的（关于f的）可增广链。

割集——容量网络D?(V,E,C),vS和vT为源和汇，若存在弧集E'?E，将网络D分为两个子图D1和D2，其顶点集合分别为S和S，S?S?V，

S?S??，vS和vT为别属于S和S，则称弧集

E'?(S,S)?{(u,v)|u ?S,v?S }

为D的一个割集。

割集容量——E'?(S,S)为容量网络D?(V,E,C)的一割集，称E'中所有弧的容量之和

C(S,S)?为E'的割集容量。

e?E'?c(e)

最小割集——容量网络D一般有多个割集，其中割集容量最小的割集称为

D的最小割集，其割集容量称为D的最小割集容量。

(2) 最大流最小割定理

定理9-1 设f为网络D?(V,E,C)的任一可行流，流量为W，(S,S)为分离vS到vT的一个割集，则有W?C(S,S)。

定理9-2 （最大流—最小割集定理）任意一个容量网络D?(V,E,C)中，从

5

源vS到汇vT的最大流的流量等于分离vS、vT的最小割集容量。

推论 可行流f是最大流的充要条件是不存在从vS到vT关于f的可增广链。 4、最小费用最大流问题

研究网络中的流时，需要注意流的可行性、高效性和经济性。实际网络中的流必须是可行流，其流量不能超过最大流的流量。网络以最小费用通过某一可行流的问题就是最小费用流问题，当网络中的流量达到最大时，就是最小费用最大流问题。

赋权容量网络——指在容量网络D?(V,E,C)中，D的每条弧(vi,vj)上除了给出最大流容量cij外，还给出了单位流量的成本dij(?0)。赋权容量网络记为

D?(V,E,C,d)。

最小费用流问题——指求赋权容量网络D的一个可行流f?{fij}，使得流量

W(f)?w*，且总费用d(f)?(vi,vj)?E?dijijf达到最小。

最小费用最大流问题——指f为最大流时的最小费用流问题。

当D?(V,E,C,d)是一个赋权容量网络，f是D上的一个可行流，Q是从源

vS到汇vT的一条关于f的可增广链，还有下列重要概念：

链的费用——称?dijfij??dijfij为Q的费用，记为d(Q)，其中Q?为Q的

Q?Q?前向弧集合，Q?为Q的后向弧集合。

最小费用可增广链——若Q*是从源vS到汇vT所有可增广链中费用最小的链，则称Q*为最小费用可增广链。

Q是关于f的从源vS到汇vT定理9-3 若f是流量为W(f)下的最小费用流，

的一条最小费用可增广链，则f经过Q调整流量?后得到的新可行流f?一定是流量为W(f)??下的最小费用流。

6

§9.2 主要解题方法和典型例题分析

题型I 求连通图的最小支撑树

1、Kruskal法

Kruskal算法的基本思想是先将网络中的边全部去除，然后逐步挑选备选边中权最小的边构成最小支撑树，并且确保与已经选好的边不产生回路。Kruskal算法也称为加边算法或避圈法。

Kruskal算法步骤如下：

第1步：将图G的m条边按权的递增顺序排列：

w(ei1)?w(ei2)???w(eim)

第2步：令l(vj)?j,j?1,2,?,n，E1??，循环变量赋值k?1； 第3步：设eik?[u,v]，若l(u)?l(v)，转第6步，否则令E1?E1?{eik}； 第4步：对满足l(vj)?max{l(u),l(v)}的vj，令l(vj)?min{l(u),l(v)}； 第5步：若E1中的边的条数|E1|?n?1，算法终止，否则继续第6步； 第6步：若|E1|?m?n?1，终止，图G为非连通图，无支撑树，否则，令

k?k?1，转第3步。

例9-1 用Kruskal算法构造图9-1的最小支撑树。

v8v1513 134181v5v11 12 10 14138 1432vvv717v6

图9-1

解：根据Kruskal算法，不断选择权最小的边，同时新增边必须与已选边不构成回路，所选边顺序：[v2,v7]，[v3,v4]，[v7,v8]，[v1,v2]，[v2,v3]，，[v5,v6]。具体步骤见图9-2(a)~(g)。

7

v8v1513 134181v5vv8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv7v8v17v6v5vv7v8v17v6 v5v(a) (b)

1513 13418111 12 10 14138 14321513 13418111 12 10 14138 1432vvvvv717v6v717v6

(c) (d)

v8v1513 134181v5vv8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv717v6v8v17

(e) (f)

1513 13418111 12 10 14138 1432v5vvvv717v6

(g)

图9-2

2、Prim算法

Prim算法类似于Kruskal算法，不同的是每次加上的边必须与前面已经加上的边连通。

对于赋权连通图G?(V,E,w)，求G的最小生成树的Prim算法步骤如下：

8