【文件属性】:
文件名称:一种简易的方法求解流量有上下界的网络中网络流问题
文件大小:177KB
文件格式:PDF
更新时间:2014-02-26 14:37:48
上下界 网络流
研究命题
一般的,定义一个网络是一个加权的有向图G = (V, E, C),E 中的每条弧(u, v)都有一个
容量上界C(u, v)≥0。
如果人为的规定V 中的两个点s 和t,其中s 没有入度而t 没有出度;并为E 中的每条弧
(u, v)赋予一个值f(u, v)≥0,f 满足以下两个条件:
①除s, t 之外的任意一个点i 都满足: ;
u i E i v E
f u i f i v
( , ) ( , )
( , ) ( , )
②任意一条E 中的弧(u, v),都满足f(u, v)≤C(u, v)。
则称f 是G 的一个可行流,称s 为流的源且t 是流的汇。前一个条件被称为流量平衡条
件,而后者则是容量限制条件。
而如果一个可行流f 使原点提供的流量 达到最大,则称f 是G 网络的最大流。
s i E
f s i
( , )
( , )
如果为G 中的每条边再加入一个容量下界:令G = (V, E, B, C),B(u, v)表示弧(u, v)的容
量下界。这样G 就是一个容量有上下界的流网络
网友评论
- 赞赞赞赞赞赞赞赞赞赞赞赞阿
- 赞!终于学会有上下界的网络流问题了
- 好文章,不错
- 不错的讲稿,讲的很详细
- 多谢,还是有很大的参考价值
- 不错,PDF格式,非常清楚