湘潭大学 刘任任版 离散数学课后习题答案 习题13.doc

习 题 十 三1 证明：对网络中的任意一个流和，均有 分析：根据定义 显然若，则在中含，而中也含，故f对端点同属于S的这种弧在中不产生影响，故有：证明：左式 2设和都是网络中的最小割，求证和也都是中的最小割. 分析：由集合的运算和容量的定义，可直接验证下式成立：又由于和都是网络中的最小割，根据最小割的定义有： 最后可得和都等于最小割的容量。证：设和都是小割，则 （1） （2）另一方面，易知 由此得 因此，是最小割类似可得也是最小割。3在图13-10所示的网络N中：（1）求N的所有割（2）求最小割的容量分析：根据定义13.1.4可知，割是分离源点x和汇点y的弧的集合。可用遍历法求出该图的所有割点及每个割得容量。解：（1）设列表如下67712511128（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），确定所有可能的流及最大流。33241233xy133241233y1(a)(b)图13-11x分析：由定义13.1.2可知，一个流f必须满足：（1）对任意（2）对任意中间点i，又f(i,V)=f(V,i)对图13-11的两个图中的每一条弧，按自上而下、自左至右的顺序进行编号，使用枚举法可确定其所有可能的流及最大流。解：对网络13-11（a）（b）的弧编号如下图所示：e9 e8 e7 e5 e4 e3 e2 e1 e6e61e9e8e7e5e3e2e1(a)(b)图13-11e4对网络(a)，遍历每条弧的流量使得f满足流的两个条件，列出可能的流如下表所示。共有44种不同的流。由于e6的流量最大为1，所以e9的流量最大也为1，而e8的流量最大为3，所以网络(a)的最大流量为4。弧流e1e2e3e4e5e6e7e8e9流的值f10000000000f21010100101f31001000101f40100100101f50100010011f60100011101f72020200202f82020111202f92020110112f102011100202f112011011202f122011010112f130200200202f140200111202f150200110112f161110200202f171110111202f181110110112f191101100202f201101011202f211101010112f223021200303f233021111303f243021110213f250300300303f260300211303f270300210213f282120300303f292120211303f302120210213f312111200303f322111111303f332111110213f341210300303f351210211303f361210210213f371201200303f381201111303f391201110213f402220310314f412211210314f423121210314f431310310314f441301210314对网络(b)，遍历每条弧的流量使得f满足流的两个条件，列出可能的流如下表所示。弧流e1e2e3e4e5e6e7e8e9流的值f10000000000f21010010011f31010011101f41001000101f50101110101f60100011101f70100010011f82011010112f92011011202f102011010112f111101011202f121101010112共有12种不同的流。由于e4、e6的流量和最大为2，所以e8、e9的流量和最大也为2。所以网络(b)的最大流量为2。6求图13-12所示网络的最大流。v3v17，64，35，34，31，13，23，23，24，24，43，24，3xy图13-12v2v4v5分析：根据定理13.2.1求网络的最大流的分析，可写出求最大流的算法如下,依据此算法可求出网络13-12的最大流。求最大流的算法：/该算法是求网络中的最大流。每条边的容量是非负整数。输入：源点为x，汇点为y，容量为C，顶点为x=v0,v1,v2,vn=y的网络和n输出：一个最大流FMax_flow(x,y,c,v,n) /v的标号是(predecessor(v),val(v) /从零流开始1For 每条边(i,j)2 Fi,j=03 While(true) /删除所有标号4 For i=0 to n 5 predecessor(vi)=null6. val(vi)=null7 /标号x8 predecessor(x)=9 val(x)=10 U=x /U是未检查、已标号的顶点集 /进行下列循环，直到y被标号11 While(val(y)=null) 12 If(U=) /当前流是最大流13 return F14 从U中选择v15 U=U-v16 =val(v)17For每条满足val(w)=null的边(v,w)18 if (Fvw0 ) 25 predecessor(w)=v26 val(w)=min, Fvw)27 U=Uw28 29 /end while(val(y)=null)循环 /找一条用来修正它上面流量的、从x到y的路径P30 w0=y31 k=032 While (wkx) 33 wk+1= predecessor(wk)34 k=k+1 35 36 P= wk+1, wk,w1,w037 =val(y)38 For i=1 to k+1 39 e=( wi, wi-1)40 if (e是P中的正向边)41 Fe=Fe+42 else43 Fe=Fe44 45 /结束while循环 解：依照上述算法，可写出如下求网络3-12的最大流的步骤。由于网络中已存在一个流，所以算法不需从零流开始。（1）执行算法步骤47，将所有顶点v，初始化predecessor(v)=null，val(v)=null（2）执行算法步骤810，初始化predecessor(x)=，val(x)=，U=x（3）执行算法步骤11，由于val(y)=null，执行while循环（4）执行算法步骤1416，从U中选择顶点x，U=，=（5）执行算法步骤1729，考虑与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）执行算法步骤1416，从U中选择顶点v1，U= v3，=1（8）执行算法步骤1729，考虑与v1邻接且满足val(v)=null的顶点4，由于不满足18和23行的if条件，所以返回到11行再次执行while循环。（9）执行算法步骤1416，从U中选择顶点v3，U=，=1（10）执行算法步骤1729，考虑与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）执行算法步骤1416，从U中选择顶点v4，U= v5，=1（13）执行算法步骤1729，考虑与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）执行步骤3237，得增广路径P=yv4v3x ，=1（16）执行步骤3843，修改路径P中的值。（17）去掉全部标记，得一新的网络如图13-13所示。v3v17，74，35，34，41，13，23，23，24，24，43，34，3xy图13-13v2v4v5（18） 对图13-13所示的网络，重复上述过程得到增广路径P=yv5v3v1x，修正P中的值。（19）去掉全部标记，得一新的网络如图13-14所示。v3v17，74，45，44，41，13，23，23，34，44，43，34，4xy图13-14v2v4v5（20）图13-14所示的网络，由于流向y的流量已达饱和，因此网络13-14中不存在任何由x到y的可增广路。该网络的流量fx,y=11为所求网络的最大流。7试证明：若在网络N中不存在有向(x, y)-通路，则最大流的值和最小割的容量都是零。 分析：若能