You*_*008 6 algorithm graph-theory graph-algorithm network-flow
我有一个边加权无向图和 2 个节点（通常称为源和汇）。我需要找到一组最小可能权重的边，它将这 2 个节点分成 2 个弱组件。
\n\n我知道Ford-Fulkerson的最大流算法以及他的最大流和最小割关系定理以及他关于有向图上的
\n\n我还知道福特-富尔克森无向图最大流算法的修改，它将每个无向边替换为 2 个相反的有向边，并同时更新它们的流。但经过此修改，最大流最小割定理似乎不再有效，因为在以下无向图上，将无法正确确定最小割：
\n\nnodes: 0, 1, 2, 3\nedges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4\nsource: 0\nsink: 3\n最大流最小割定理说，最小割是那些流量等于其容量的边，而根据修改后的福特-富尔克森，这是所有边，这显然不是正确的割。
\n\n我找到了一个Stoer\xe2\x80\x93Wagner 算法，用于在无向图中查找全局最小割，但这不是我想要的，因为该算法不考虑任何源和汇，并且可以找到一个cut，这让节点位于同一个组件中。
\n\n是否有任何算法可以有效地在具有源和接收器的无向图中找到最小切割，将这两个指定的节点分开？\n我可以以某种方式修改前面提到的算法以使它们适用于我的情况吗？
\n小智 0
您可以使用 Ford-Fulkerson 算法的一些修改。
当您找到最大流时，只需将无向边视为具有相同容量的两条有向边即可。