algorithm - 网络中的最小 s-t 切割

Question

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

我有一个具有一些边缘容量的节点网络。这相当于算法中的网络流问题。有一个源节点(检测某些事件)和一个接收节点(我的基站)。现在，我想在网络中找到最小的 s-t 切割，以便最小化源集的大小。这里的源集是指被包含源的 min s-t cut 分隔的节点集。

例如如果 s-t 切，C = {S,T} ，然后有一组边可以被删除以将网络分成两组，S和 T和套装 S包含来源和 T包含水槽。在所有可能的 s-t 切割中，当切割中边的容量总和最小时，切割最小。可以有几个这样的最小剪辑。我需要找到集合中元素数量最少的最小切割S
请注意，这不是最初的问题，但我试图简化它以便用算法来表达它。

Answer 1

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

更正式地，构造如下。给定一个有向、有容量的图 G 和一个(源、汇)对 (s, t)，通过执行以下操作构建图 G':

对于图中的每条边 (u, v)，将其容量乘以 n。

对于图中的每个节点 v，添加一条容量为 1 的新边 (v, t)。

计算图中的最小 s-t 切割。

我声称图 G' 中的最小 s-t 割对应于图 G 中的最小 s-t 割，在割的同一侧与 s 的节点数最少。证明如下。令 (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'，G 中 (S, V - S) 的成本为 C。现在，让我们考虑 G' 中这两次切割的成本。通过收缩，C' 的成本将是 nC' + |S'| (因为切割的 S' 侧的每个节点在整个切割中贡献一个容量)并且 C 的成本将为 nC + |S|。因为我们知道 C' < C，所以我们必须有 C' + 1 ≤ C。因此

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

现在，请注意 0 ≤ |S| < n 且 0 ≤ |S'| < n，因为在切割的同一侧最多可以有 n 个节点作为 s。因此意味着

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

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

现在，我们需要证明不仅 G' 中的 min st 切割也是 G 中的 min st 切割，而且它对应于 G 中与 s 同一侧的节点数最少的 G 中的 min st 切割.同样，这个证明是自相矛盾的；假设 (S, V - S) 是 G' 中的最小 s-t 切割，但 G 中有一些最小 s-t 切割，切割的 s 侧的节点较少。称之为更好的切割 (S', V - S')。由于 (S, V - S) 是 G' 中的最小切割，它也是 G 中的最小切割，因此 G 中的 (S', V - S') 和 (S, V - S) 的成本为一些数字 C。那么 G' 中 (S, V - S) 和 (S', V - S') 的成本将是 nC + |S|和 nC + |S'|，分别。我们知道 nC + |S'| < nC + |S|，因为我们已经选择 (S', V - S') 作为 G 中与 S 同一侧节点数最少的 st min 切割。但这意味着 (S', V - S') 的成本低于 (S, V - S)，这与 (S, V - S) 是 G' 中的最小 st 切割相矛盾。因此，我们的假设是错误的，并且 (S, V - S) 是 G 中与 S 同一侧节点数最少的最小 s-t 切割。这就完成了构造的正确性证明。

希望这可以帮助!