习 题 十 三
1． 证明：对网络中的任意一个流
和
，均有
分析：根据定义
显然若，则在
中含
，而
中也含
，故f对端点同属于S的这种弧在
中不产生影响，故有：
证明：
左式
2．设和
都是网络
中的最小割，求证
和
也都是
中的最小割.
分析：由集合的运算和容量的定义，可直接验证下式成立：
又由于和
都是网络
中的最小割，根据最小割的定义有：
最后可得
和
都等于最小割的容量。
证：设和
都是小割，则
（1）
（2）
另一方面，易知
由此得
因此，是最小割
类似可得也是最小割。
3．在图13-10所示的网络N中：
（1）求N的所有割
（2）求最小割的容量
分析：根据定义13.1.4可知，割是分离源点x和汇点y的
弧的集合。可用遍历法求出该图的所有割点及每个割得容
量。
解：（1）设列表如下
（2）比较可得最小割的容量为5。
4．证明推论13.1.1
分析：推论13.1.1描述了网络N的任意流值与任意割的容量的关系，即
该题的证明用到了流的定义及定理13.1.1的结论。
证明：由定义13.1.2可知，一个流f必须满足：对任意
因此有
又由定理13.1.1有，对任意流f的值，和任意割
有：
因此有
5．对于图13-11中的（a）和（b），确定所有可能的流及最大流。
分析：由定义13.1.2可知，一个流f必须满足：
（1）对任意
（2）对任意中间点i，又f(i,V)=f(V,i)
对图13-11的两个图中的每一条弧，按自上而下、自左至右的顺序进行编号，使用枚举法可确定其所有可能的流及最大流。
解：对网络13-11（a）（b）的弧编号如下图所示：
对网络(a)，遍历每条弧的流量使得f满足流的两个条件，列出可能的流如下表所示。
共有44种不同的流。
由于e6的流量最大为1，所以e9的流量最大也为1，而e8的流量最大为3，所以网络(a)的最大流量为4。
对网络(b)，遍历每条弧的流量使得f满足流的两个条件，列出可能的流如下表所示。
共有12种不同的流。由于e4、e6的流量和最大为2，所以e8、e9的流量和最大也为2。
所以网络(b)的最大流量为2。
6．求图13-12所示网络的最大流。
分析：根据定理13.2.1求网络的最大流的分析，可写出求最大流的算法如下,依据此算法可求出网络13-12的最大流。
求最大流的算法：//该算法是求网络中的最大流。每条边的容量是非负整数。
输入：源点为x，汇点为y，容量为C，顶点为x=v0,v1,v2,…,vn=y的网络和n
输出：一个最大流F
Max_flow(x,y,c,v,n)
//v的标号是(predecessor(v),val(v))
//从零流开始
1．For 每条边(i,j)
2． Fi,j=0
3． While(true) {
//删除所有标号
4． For i=0 to n {
5． predecessor(vi)=null
6. val(vi)=null
7． }
//标号x
8． predecessor(x)=—
9． val(x)=∞
10． U={x} //U是未检查、已标号的顶点集
//进行下列循环，直到y被标号
11． While(val(y)==null) {
12． If(U==φ) //当前流是最大流
13． return F
14． 从U中选择v
15． U=U-{v}
16． ε=val(v)
17．For每条满足val(w)==null的边(v,w)
18． if (Fvw
19． predecessor(w)=v
20． val(w)=min{ε, Cvw —Fvw)
21． U=U∪{w}
22． }
23．For 每条满足val(w)==null的边(w,v)
24． if (Fwv>0 ) {
25． predecessor(w)=v
26． val(w)=min{ε, Fvw)
27． U=U∪{w}
28． }
29． }//end while(val(y)==null)循环
//找一条用来修正它上面流量的、从x到y的路径P
30． w0=y
31． k=0
32． While (wk≠x) {
33． wk+1= predecessor(wk)
34． k=k+1
35． }
36． P={ wk+1, wk,…w1,w0}
37． ε=val(y)
38． For i=1 to k+1 {
39． e=( wi, wi-1)
40． if (e是P中的正向边)
41． Fe=Fe+ε
42． else
43． Fe=Fe—ε
44． }
45． }//结束while循环
}
解：依照上述算法，可写出如下求网络3-12的最大流的步骤。由于网络中已存在一个流，所以算法不需从零流开始。
（1）执行算法步骤4—7，将所有顶点v，初始化predecessor(v)=null，val(v)=null
（2）执行算法步骤8—10，初始化predecessor(x)=—，val(x)=∞，U={x}
（3）执行算法步骤11，由于val(y)=null，执行while循环
（4）执行算法步骤14—16，从U中选择顶点x，U=φ，ε=∞
（5）执行算法步骤17—29，考虑与x邻接的顶点1,2,3：
得predecessor(v1)= predecessor(v3)=x；val(v1)=1 val(v3)=1；U={ v1，v3}
（6）执行算法步骤11，由于val(y)=null，再次执行while循环
（7）执行算法步骤14—16，从U中选择顶点v1，U={ v3}，ε=1
（8）执行算法步骤17—29，考虑与v1邻接且满足val(v)=null的顶点4，由于不满足18和23行的if条件，所以返回到11行再次执行while循环。
（9）执行算法步骤14—16，从U中选择顶点v3，U=φ，ε=1
（10）执行算法步骤17—29，考虑与v3邻接且满足val(v)=null的顶点4和5：
得predecessor(v4)= predecessor(v5)= v3；val(v4)=val(v5)=1；U={ v4，v5}
（11）执行算法步骤11，由于val(y)=null，执行while循环
（12）执行算法步骤14—16，从U中选择顶点v4，U={ v5}，ε=1
（13）执行算法步骤17—29，考虑与v4邻接且满足val(v)=null的顶点y：
得predecessor(y)= v4；val(y)=1；U={y，v5}
（14）执行步骤11，由于val(y)=1，退出while循环，转向步骤30执行，初始化w0=y， k=0
（15）执行步骤32—37，得增广路径P=yv4v3x ，ε=1
（16）执行步骤38—43，修改路径P中的值。
（17）去掉全部标记，得一新的网络如图13-13所示。
（18） 对图13-13所示的网络，重复上述过程得到增广路径P=yv5v3v1x，修正P中的值。
（19）去掉全部标记，得一新的网络如图13-14所示。
（20）图13-14所示的网络，由于流向y的流量已达饱和，因此网络13-14中不存在任何由x到y的可增广路。该网络的流量fx,y=11为所求网络的最大流。
7．试证明：若在网络N中不存在有向(x, y)-通路，则最大流的值和最小割的容量都是零。
分析：若能利用已知条件构造出一个割，其容量等于零；同时还能构造一个流，其流量也为零，则根据定理13.2.1，可知：最大流的值和最小割的容量都是零。
证明：令S={v| 在N中存在（x,v）-有向路}。
显然x∈S，又在网络N中不存在有向(x, y)-有向路，所以，因此(S，
)构成N的一个割，且C(S，
)=0。
又零流；，了f0的流量fx,y=0。
根据定理13.2.1，N中最大流的值和最小割的容量都是零。
本文来源：https://www.2haoxitong.net/k/doc/555bbe85f8c75fbfc77db2b6.html
文档为doc格式