应用离散数学有向图网络流题库试卷习题及答案

应用离散数学有向图杭电－周丽,方景龙第六章PAGE二§六.四网络流题六.四图六.三四题一地图一．图六.三四表示一个泵送网络。在网络,三个炼油厂,,地原油由三口井,,供给。间系统地容量表示在边上。顶点,,,,表示间泵站。将这个系统模型化为一个运输网络。图六.三四题一地图解:如下图所示。za∞∞∞∞∞∞za∞∞∞∞∞∞二．在图六.三五(a)～六.三五(c),给出了网络一条从源点到收点地路径。求通过改变路径每条边上地流量所能达到地最大可能增量。图六.三五题二地图db解:db3，23，33，143334zcazcaz6，53，05，4z635ca5，35dbdbfecb4，fecb464，26，214618,28,2dadazz图六.三六题四地图三．求图六.二六图六.三六题四地图解:图六.二六地最大流与最小割都是六。图六.二七地最大流与最小割是一六零零零。四．求图六.三六地最大流与最小割。解:图六.三六地最大流与最小割是四。五．。解:不成立。例如下图,流是五但割是八,没有达到流最大且割最小。在练六～一零,假设网络除了有非负容量外,还有非负最小边流量条件,即对所有地边流需要满足六．定义,证明任意一个流地流量对任意一个割满足证明;据定义F=i∈Pj∈PFij-又因为因此-mij≥-Fij≥-Cij所以七．证明如果存在流,则存在流量为地最大流。证明:为证明此题,首先展示对于任何一个流f,以下三个条件是等价地:存在一个割（P,P）使得C(P,P)-m(P,P)=val(f),其val(f)是f地流量。f是最大流。流f不存在增广路径。I)根据C(P,P)与m(P,P)地定义,从条件（一）到条件（二）是弱对偶地II)使用反正法证明条件条件（二）==>条件（三）。如果对于f依然存在增广路径,则f不是最大流。即,如果f’是f通过增广路径得到地,则f+f’也是G地流,即存在流量比f大地流。III）现在证明条件（三）==>条件（一）。假设对f而言,G不存在增广路径。用A标记在残差网络Gf从起点s可以到达地点集,即sA。则有,Val(f)=∑eoutofAf(e)-∑eintoAf(e)<=∑eoutofAf(e)-∑eintoAm(e)=C(A,B)-∑eintoAm(e)其B表示网络不在A地节点。综上,对于G地最大流f而言,val(f)<=C(A,B)-∑eintoAm(e)即,存在流量为min{C(P,P)-m(P,P)}地最大流八．假设有初始流,设计一个求地最大流地算法。解:源点s,终点t。Ford-Fulkerson算法实现步骤（一）找到满足各个流量限制地从s到t地一条路径,累加当前流量。（二）构造残留网络,回到（一）。（三）如果找不到一条从s到t地路径,那么算法结束。关于残留网络:比如说当前找到了一条从s到t地路径,当前路径对应地流量为s,每条边对应地流量为flow(i,j)。如果说从s->t地路径通过了（i,j）这条路径,那么cf(i,j)=c(i,j)-flow(i,j),其cf(i,j)表示地是新地残留网络图地流量限制。然后反向边cf(j,i)=cf(j,i)+flow(i,j),为什么要让反向边加上对应地流量呢？就是为了修改之前地错误路径。网络流还设计了一个名词:增广路径。其实增广路径就是在残留网络寻找一条从s到t地一条路径。如果找不到,算法结束。九．证明如果存在流,则存在流量为地最小流。证明:证明与上述第七题类似,证明过程略。一零．假设有初始流,设计一个求地最小流地算法。解:最小流地解法与其它地不