什么是网络流的割？什么是网络流的最小割？

什么是网络流的割？什么是网络流的最小割？

前一向学会最大流的几个写法~~FF..EK...Dinic...就以为自己会网络流了...今天去做hh大牛的网络流习题...发现自己除了最大流....建图以及其他性质神马的都一片空白....拿到一个题..无从下手来建图....网上搜了一下网络流的建图策略与方法...很多大牛提到最小割...我知道求最小割求出最大流就行了...最大流和最小割的值是相等的...但我一直没搞懂最小割是什么...网上搜了一些最小割的资料....都比较含糊....后来去Google了一个英文资料....几张图让我一下明白网络流的割是个什么东西...:

a

.割的容量只记从S点集到T点集的....T点集到S点集的不算...所以割的容量等于这从S点集到T点集所有边的容量之和...

而网络流的最小割就是这些割中容量最小的....

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。