多路切割 Q-我们如何在多面时间内显示解决方案?

Question

在多路切割问题中，输入是一个无向图G=(V，E)和一组终端节点s1，s2....sk 在 V 中。

Answer 1

这听起来像是家庭作业，但这里有一个提示：如果将图形转换为每个边的容量为 1 的流网络，并使用两个终端节点作为源和汇，则可以使用 Edmonds-Karp 在多项式时间内查找两个终端节点之间的流。当你找到最大流量时，最小切割最大流量定理告诉你什么？

Answer 2

1. 这个问题确实可以通过最小切割最大流量来解决，正如 @Aasmund Eldhuset 所指出的那样，S1，S2 之间的最小切割实际上是您需要移除的最小边集，以便分离 S1 和 S2。
   请记住，最小切割问题说：

   给定一个图形(加权，但您可以使用w(e)=1用于所有边 未添加版本)，找到具有组合最小权重的边缘集 - 这样源 (S1) 和接收器 (S2) 将位于不同的连接组件中。

   请注意，这个问题正是你的问题 - 并且可以通过一些算法来解决，例如Edmond Karp - 它在多项式时间内运行

2. 通过重复 (S1，S2) 和 (S2，S3) 的过程，您可以获得 2 组边 E1(对于 S1，S2)和 E2(对于 S2，S3)。
   现在，请注意，最佳解决方案(让它成为 OPT)并不比 E1 和 E2 都小(否则 - 因为 OPT 的"切割"将 S1、S2 和 S2、S3 分开 - 它将作为答案返回而不是 E1 或 E2。
   由此我们可以得出结论|OPT| >= max{|E1|,|E2|}.请注意，|E1 Union E2| <= |E1| + |E2| <= |OPT| + |OPT| = 2|OPT|- 因此E1 Union E2是 poblem 的 2 近似值。