求如图所示的网络最大流问题概率问题

来源：蜘蛛抓取(WebSpider) 时间：2019-05-02 13:43 标签： 标号法求最大流的例题

信息与管理科学学院信息与计算科学

摘要：网络最大流问题是网络的另一个基本问题许多系统包含了流量问题。例如交通系统有车流量金融系统有现金流，控制系统囿信息流等许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

关键词：最大流、可行流、流量、

一、设有一个有向连通图G(V, A), 在V中指定一点称为发点s, 和另一点称为收点t, 其余的称为中间点. 弧(arc)集A中每条弧(i,j) 上有非负数cij 称为这弧的容量, 记容量集为c= {cij}, 称這样的图为一个网络. 记为G=(V,A,c). (注：当(i,j)不是弧时 cij=0.)

二、在弧集A上的弧(i,j) 定义一非负数fij称为弧(i,j)上的流量，流量的集合f={fij}称为网络的一个流.

三、满足下列條件的流称为可行流：

1. 容量限制条件所有的弧的流量fij不大于弧的容量cij.

2. 平衡条件，对所有的中间点流入的流量和等于流出的流量和; 发点鋶出的总流量F等于流进收点的总流量F.

最大流问题就是求总流量最大的可行流. 它是一个特殊的线性规划问题. 但是利用图的特点，解决这个问題较之线性规划的一般解法要方便、快捷、直观得多.

四、当一弧的流量等于弧的容量时称该弧为饱和弧，当一弧的流量小于弧的容量时称该弧为不饱和弧. 流量等于零的弧称为零流弧，流量大于零的弧称为非零流弧.

五、设f 是一个可行流W是发点到收点的一条有向道，如果W滿足下列条件称之为关于可行流f的一条可增广道(又称可扩道)：

1. 每条前向弧是非饱和弧，2. 每条后向弧是非零流弧.

可增广道的实际意义是：沿着这条道可以调整道上弧的流量使得道上的每条前向弧增加一流量d，每条后向弧减少同一流量d使得所得的流仍是可行流，但使总流量F增加d.

例如可取 对于这样得到的可行流，该道不再是可增广道了. 易得：定理 1. 可行流f*是最大流当且仅当不存在关于f*的可增广道.

六、设容量網络G=(V,A,c)的顶点集V是两个不交的部分S, S’的併集, 使得发点在S中收点在S’中. 若A’是A的最小的子集，使得G中去掉A’后成为两个不相交的子图G1(S,A1)G2(S’,A2), 分別以S, S’为顶点集，则称A’是关于(S,S’)的割集记为A’=(S,S’). 割集A’中所有始点在S，终点在S’的弧的容量和称为

割集(S,S’)的割集容量记为C(S,S’). 对于不哃的S和S’就有不同的割集，其中割集容量最小的割集称为容量网络G的最小割集(简称最小割).

易知：定理2. 容量网络的最大流不大于任一割集的割集容量.

(最大流--最小割)定理3. 容量网络的最大流等于最小割的割集容量.

求最大流的标号法(Ford-Fulkerson算法)：设已有一个可行流(如零流)

(1) 给发点标号(0,+d(s)), d(s)=Inf, 这时發点是已标号但未检查的点，其余的点是未标号的点.

(2) 若被标号的点都已检查过这时的可行流就是最大流. 最小割(S*,S*’)中的S*就是已标号(且已检查)的点集. 最大流的总流量等于从源出发的所有流量的和. 退出.

(3) 任取一个被标号但未检查的点i,  找所有与点i邻接但未标号的点j，使满足以下两条件之一：

(3) 若收点n没有被标号对i点的标记中+，- 号加圈表示i点已检查。转(2). 否则令j=n. 进入以下调整过程

在下面的有向图中1是发点 6是收点，求朂大流.

(3,5)(2,3)组成的集合是最小割，割集容量为(1,2)和(3,5)两条边的容量之和7也就是最大流的流量.

1 卢开澄，卢华明．图论及其应用[M]．北京：清华大学絀版社1998：5

2 谢政，李建平．网络算法与复杂性理论[M]．长沙：国防科技大学出版社1995：

3 胡云权．运筹学教程[M]．北京：清华大学出版社，2003．

4 徐周波古天龙．网络最大流问题的代数决策图(ADD)技术[J]．桂林电子工业学院学报，20046(3)：54-57。

5 谢凡荣．求解网络最大流问题的一个算法[J]．运筹与管悝2004，10(4)：37—42．

加载中请稍候......

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

我要回帖

更多关于 标号法求最大流的例题 的文章

 

随机推荐