时间戳

首页 > 解决方案 > Max Flow/Minimum Cut - 去除 K 边算法后的流量

algorithm - Max Flow/Minimum Cut - 去除 K 边算法后的流量

问题描述

我被要求为以下问题开发一种算法：

给定：

  1. 一个流网络 G，其边的最大容量为 1
  2. G的最大流量|F|
  3. 一个正整数 K

准确删除 K 条边，使网络的流量最小化。

我的想法/算法：

  1. 如果 K 大于或等于 |F| 删除所有穿过 G 的最小切割的边，如果 K 仍然大于零，则删除随机边并且新的最大流量为零

  2. 如果 K 等于 |F| 删除所有穿过 G 的最小割的边，新的最大流量为零

  3. 如果 K 小于 |F| 删除穿过 G 的最小割的K条边，新的最大流为 |F|-K

我需要一些验证，因为 Max Flow/Min Cut 对我来说是新的。最后，我得到的 Max Flow/Min Cut 背后的直觉是 Min（Source，Sink）cut 是我们可以在网络中推送的最大流量的“瓶颈”。对吗？

标签： algorithmgraph

解决方案

是的，最小切割也是流量的“瓶颈” |Min-Cut| = Max-flow。如果你有兴趣，网上有大量的证明（它被称为最大流量最小切割定理）。

对于您的算法，无需在第一步中删除随机边，从 min-cut 中删除一条边会减少通过该边的流的最大流（在这种情况下，1因为所有权重都1根据语句）。

所以解决方案就是：

  1. 找到任何最小切割
  2. 从图中删除min(K, |Min-cut|边）

找到 Min-Cut 可以很容易地完成：

  1. 构建剩余流图
  2. 在其上运行任何最大流量算法（Ford-Fulkerson、Bellman-Ford 等）
  3. 现在从源节点做 BFS，只通过流量值小于容量的边
  4. 现在从访问节点到未访问节点的所有边形成一个最小切

推荐阅读