网络中的最小 s-t 割

Question

我正在模拟一个无线传感器节点网络，以研究网络的稳健性。我面临以下问题：

我有一个带有一些边容量的节点网络。这相当于算法中的网络流问题。有一个源节点（检测某些事件）和一个汇节点（我的基站）。现在，我想找到网络中的最小s-t割，以便最小化源集的大小。这里的源集是指包含源的min s-t cut分离的节点集合。

例如，如果s-t cut为C = {S,T}，则有一组可以删除的边，将网络分成两个集合S和T，并且集合S包含源，T包含汇。当割的边的容量之和在所有可能的s-t割中最小时，割是最小的。可能会有几个这样的最小割。我需要找到一个具有最少元素的集合S的最小割。

请注意，这不是原始问题，但我已经尝试简化它，以便用算法术语表达。

- user760955

---

确认一下 - 您想要包含与 s 相同分区中最少节点的 s-t 最小割吗？ - templatetypedef

https://cs.stackexchange.com/q/117932/755 - D.W.

Answer 1

我相信您可以通过在稍微修改的约束条件下找到图中的最小割来解决这个问题。其思想如下 - 由于割的成本等于横跨割的总容量，因此我们可以尝试通过向图中的每个节点添加一条从该节点到t的容量为1的额外边来修改图形。直观地说，这意味着与s处于同一部分的每个节点都会对割的总成本贡献一个额外的成本，因为从该节点到t的边将穿过该边。当然，由于额外的容量，这肯定会搞乱实际的最小割。为了解决这个问题，我们应用以下变换 - 首先，将边的容量乘以n，其中n是图中节点的数量。然后给每个边加上1。这里的直觉是，通过将边缘容量乘以n，我们使得最小割的成本（忽略每个节点到t的新边）将是割的原始成本的n倍。当我们然后添加从每个节点到t的额外的一容量边时，这些边可能对割的成本产生的最大贡献是n-1（如果除t之外的图中每个节点都在与s相同的一侧）。因此，旧最小切割的成本是C，新最小切割（S，V-S）的成本是nC + |S|，其中|S|是与s在同一侧的节点数。

更正式地说，构造如下。给定一个有向容量图G和一个（源，汇）对（s，t），通过执行以下操作构建图形G'：

1. 对于图中的每条边（u，v），将其容量乘以n。 2. 对于图中的每个节点v，添加一个容量为1的新边（v，t）。 3. 计算图中的最小s-t割。

我认为，图G'中的最小s-t割对应于在图G中与切割边在同一侧节点数量最少的最小s-t割。证明如下。假设(S, V-S)是G'中的最小s-t割，我们首先需要证明(S, V-S)也是G中的最小s-t割。采用反证法；为了矛盾，假设存在一种s-t割(S', V-S')，其成本低于(S, V-S)的成本。令G中(S', V-S')的成本为C'，(S, V-S)的成本为C。现在，让我们考虑这两个割在G'上的成本。根据约束条件，C'的成本将为nC'+|S'|（因为切割点S'侧的每个节点都对切割线贡献了一个容量），而C的成本将为nC+|S|。由于我们知道C'

nC+|S| ≥ n(C'+1)+|S|=nC'+n+|S|

现在，注意到0≤|S|<n且0≤|S'|<n，因为与s在同一侧的节点最多可以有n个。这意味着

nC+|S| ≥ nC'+n+|S|>nC'+|S'|+|S|>nC'+|S|

但这意味着在G'中，(S, V-S)的成本大于G'中(S', V-S')的成本，这与(S, V-S)是G'中的最小s-t割的事实相矛盾。这使我们得出结论：G'中的任何最小s-t割也是G中的最小s-t割。

现在，我们需要证明，在G'中的最小s-t割不仅是G中的最小s-t割，而且它对应于G中与s同侧节点数量最少的最小s-t割。同样，这个证明采用反证法；假设(S，V-S)是G'中的最小s-t割，但是在G中存在一些比S侧节点更少的最小s-t割。将这个更好的割称为（S'，V-S'）。由于（S，V-S）是G'中的最小s-t割，它也是G中的最小s-t割，因此（S'，V-S'）和（S，V-S）在G中的成本都是C。然后，G'中（S，V-S）和（S'，V-S'）的成本分别为nC + |S|和nC + |S'|。我们知道nC + |S'| < nC + |S|，因为我们选择（S'，V-S'）作为在G中与S侧节点数量最少的s-t最小割。但这意味着（S'，V-S'）的成本低于（S，V-S），这与（S，V-S）是G'中的最小s-t割的事实相矛盾。因此，我们的假设是错误的，（S，V-S）是G中与S同侧节点数量最少的最小s-t割。这完成了构造的正确性证明。希望这可以帮到您！

- templatetypedef

Answer 2

计算最大的s-t流，并让S成为从s到具有正剩余容量的弧可达的节点集。

正确性证明：显然，S是最小的s-t割（割=包含s的一部分节点集）。假设S*是比S更小的s-t割（即，|S*| < |S|）。通过简单的计数，设u是在S-S*中的一个节点。如果我们向t添加一个正容量弧，那么计算出的流就具有增广路径，并且不再是最大的，但是由于u和t都属于V-S*，因此割S*的容量保持不变。我们通过弱对偶性得出结论，S*不是最小割。

事实上，s-t最小割的类是在交集和并集下的分配格，因此您的问题的每个实例都具有唯一的解决方案。

- Per

---

这是正确的，但 OP 所要求的不是一般的 s-t 最小割，而是在割中 s 侧节点最少的 s-t 最小割。 - templatetypedef

@templatetypedef 是的，这就是为什么我特别证明了切割返回最小化包含 s 的部分的基数。 - Per

@Pre- 但是可能存在许多具有不同基数的s-t最小割。我不确定您的证明如何处理这种情况，因为一个割可能比另一个割具有更多的节点。 - templatetypedef

@templatetypedef 是的，可以有许多最小的s-t割（作为包括s但不包括t的节点子集）。这些最小的s-t割在交集和并集下形成一个格。所有这些割的交集是具有最小基数的最小s-t割，证明表明它是算法找到的那个。 - Per

@Per 是的，你的算法很完美！我现在明白了。真的很简单和正确。 - user760955

Answer 3

在你的问题和评论中，我认为你说了两件不同的事情。首先，找到最小的s-t割，使得它将源节点和目标节点分开，并且其权重是最小的（权重将通过删除边缘大小来计算），这可以使用Ford-Fulkerson算法完成，这里有Java的示例实现（Matlab也有一个graphmaxflow函数），同时它也可以在{{link2：igraph}}库中使用。

但是根据你的评论和问题的第一部分，你要求找到最小割，使得s部分中节点的数量最小，在这种情况下，你应该删除所有从S出发的边缘，以便形成一个大小为1，n-1的组，或者你应该重新表述你的问题。

- Saeed Amiri

---

抱歉！我已经重新表述了我的问题。 - user760955