随笔 - 40, 文章 - 0, 评论 - 19, 引用 - 0
数据加载中……

最大流最小割定理证明

最大流最小割定理:最大流等于最小割,即max V(f) = min C(U, W)。


说明,自己的证法,如有错误请大家提出:
声明:最大流=|f|,割为=|[S,T]|
1、|[S,T]| >=  |f| (易知,最大流可能比管子粗细还大?)
2、有如果有Df( |[S,T]| ) = 0 ,则一定是最大流(否则最大流的多于|[S,T]|的流量从何处流...)
3、如果当前流量已经最大,从源到汇的任意一条路径一定有饱和边(增广路法则)
4、*反证,如果对任意S,T没有Df( |[S,T]| ) = 0
   取S ={源点},T={V-S};则有源点连接未饱和管道的另一端点K,然后取S={源点,K},T={V-S},则有源点连接未饱和管道的另一端点K1,然后取S={源点,K,K1},T={V-S},则有源点连接未饱和管道的另一端点K2.........当V-S = 汇点,我们发现源点,K,K1,K2,K3....汇点,为一条增广路(可能K1,K2不相连,而直接源点,K,K2)
 得证。

posted on 2010-04-26 16:03 hadn't 阅读(2806) 评论(2)  编辑 收藏 引用

评论

# re: 最大流最小割定理证明  回复  更多评论   

好不容易看到一个清晰的说明 DF是什么意思 操你妈 写中文会死? 不洋气会死? 逗比
2014-01-26 15:04 | LZSB

# re: 最大流最小割定理证明  回复  更多评论   

@LZSB
终于看懂了 还好哥机智 还是谢谢了
2014-01-26 15:41 | LZSB

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理