在图中找到最小切割，以便给定顶点断开连接

作者: v-star*위위
发布时间: 2025-02-07 03:18:02 (20天前)
转自：

2 条回复

0#
回复此人
银角 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 有几种算法（见 <a href="http://en.wikipedia.org/wiki/Maximum_flow_problem" rel="noreferrer"> 维基 </A> 在介绍中找到网络中的最大流量。那些我认识的人（Ford-Fulkerson，Dinic，Karp-Edmond）应该表现出良好的单位容量（= <EM> 所有边上的整数容量等于1 </EM> ）（可变容量会增加复杂性，而非整数容量会产生更多问题） </p> <P> 对于任何一对顶点，您可以通过将source / sink设置为此对来从图形创建网络。您可以使用其中一种算法获得最大流量，您可以使用这些算法进行如下切割： </p> <UL> <LI> 选择流使用的任何边。这条边将属于切割。 </LI> <LI> 重复，但现在在没有选定边的图上进行流搜索，直到流为0 </LI> </UL> <P> 最后，您有最小切割，最大流量的大小。 </p> <P> 如果您真的想要按性能，可能需要查看本文： <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.116" rel="noreferrer"> 无向单位容量网络中的流量（1997年） </A> 作者：Andrew V. Goldberg，Satish Rao，但我可能会坚持使用更简单的那些。 </p> </DIV>

编辑

登录后才能参与评论