问题标签 [ford-fulkerson]

我想在具有整数容量的流网络 G 中的所有最小切割中找到包含最少边数的切割。我们如何修改 G 的容量以创建一个新的流网络 G'，其中 G' 中的任何最小割都是 G 中边数最少的最小割。来源 - Cormen

我正在尝试找到以下网络的最小切割

我正在使用以下算法：

1. 运行 Ford-Fulkerson 算法并考虑最终的残差图。

2. 在残差图中找到从源可到达的顶点集。

3. 从可达顶点到不可达顶点的所有边都是最小割边。打印所有这些边缘。

第一步，我的算法找到了 3 条路径：

所以最大流量（因此最小切割）等于 2.5。

但是，当我后来尝试从网络中消除上述路径时，我最终得到了这样的结果：

可达顶点是 s、c 和 h，它们形成一个等于 3.5 的割。

我错过了什么？为什么我不能像通常那样遍历图表以获得最小切割？

福特富尔克森复杂性是O(FE)，但埃德蒙卡普斯是O(VE^2)。这是基于每条边只能达到临界O(V)次数的前提，这适用于所有边，所以我们有O(VE)边可能达到临界的次数，即可以找到增广路径的次数。这是有道理的，因为我们可以O(V)多次使用 1 条边，然后因为我们需要对图中的所有其他边都这样做，所以我们有O(VE)时间需要找到增广路径。然后是BFStake O(E)，所以我们得到了最终的 edmonds karp 复杂度。

但问题是：O(VE)关于增广路径数量的论点如此笼统，那么为什么不能将这种分析应用于福特富尔克森呢？似乎在不公平的基础上比较了两种算法的复杂性。edmonds karp 算法的优势是什么？

另外，为什么当我们在 edmonds karp 中使用 BFS 方法时，我们可以保证找到最短路径？有一个简短的证明吗？

我们得到一个网络流量，以及网络中的最大流量。如果以任意正数增加其容量，则边缘将被称为增加边缘，也会增加最大流量。

提出一种算法，找到一个增加的边缘（如果存在）并以 $O(n^2)$ 运行。

我想到了以下想法——

• 找到图中的最小割，因为它是用福特-富尔克森算法给我们的。
• 将切口左侧所有边的容量增加 1。
• 在残差网络中运行 BFS 以查找是否存在改进的路径。如果存在，我们将拥有越来越大的优势。要找到它，我们必须将原始网络与新网络进行比较。我们必须这样做 n 次，因为每次我们将容量增加 1 时都必须检查改进的路径。

是否正确，我是否符合所需的运行时间？

谢谢！

给你一个 nxn 棋盘，上面有 k 个骑士（相同颜色）。有人在 k 个方格上洒了强力胶，如果骑士在其中一个方格上完成移动，它就会永远卡住。此外（这就是为什么我们不能拥有好东西的原因）有人切掉了一些方格，所以棋盘上有洞。您将获得骑士的初始位置。骑士像在普通国际象棋中一样移动，但与普通国际象棋不同的是，每回合所有的骑士都会同时移动（当然，被卡住的骑士除外）。在每一步结束时，一个方格不能被超过 1 个骑士占据。洞格也不能被骑士占据（但它们确实算作骑士可以跳过的格子）。给出一个 0(tx poly(n))-time 算法来判断是否可以使用 <

我最初的想法是将这个问题表述为一个最大流问题，并使用 Ford-Fulkerson 算法来解决它。但我不确定我的节点和边缘应该是什么。任何想法？谢谢！

如果有人可以帮助我，那就太好了。

我有一个无向图，其中每个顶点都有权重，而没有边有权重。我想找到一组总权重最小的节点，它们的删除会使图表断开连接。例如，在删除一个权重为 10 的节点使图断开连接和删除总权重为 6 的 2 个节点使图断开连接之间，结果集应包含这 2 个节点。

这个问题有什么已知的算法吗？

这是我到目前为止所做的。我使用networkx（python）制作了我的代码。我已经将我的图表更改为定向。例如，对于节点 1，我考虑 1in 和 1out 节点。我通过节点 1 的权重将 1in 连接到 1out。我还添加了 s 和 t 节点（我不确定它是否正确）。我还定义了新有向图中每条边的容量。

运行代码时，我收到此错误：NetworkXUnbounded: Infinite capacity path, flow unbounded above.

谢谢

嗨，我在使用max-flow min-cut Theorem研究 Ford-Fulkerson 算法时遇到了麻烦。

根据定理，最大流量应与被切割边的总重量相同。

但是，看到视频https://www.youtube.com/watch?v=Tl90tNtKvxs让我感到困惑。讲师说根据 Ford-Fulkerson 算法，最大流量为 19，但我找不到任何削减 19 的费用。出了什么问题？

我有以下两个问题。

1. 对或错：我们总是可以在 Ford-Fulkerson 算法中找到一系列流增强 st 路径，这样我们就可以在多项式迭代中达到最大流。
2. 对或错：我们总是可以在 Ford-Fulkerson 算法中找到一系列流增强 st 路径，这样我们只有在指数级迭代后才能达到最大流。

我在理解用于查找最大流量的 Ford-Fulkerson 算法时遇到了一些麻烦，希望能得到一些帮助。

如果我们看下图，其中源 A 和汇 F 列出了每条边的边容量。

您会注意到节点 B 和 C 有一条双向边，BC 的容量为 8，CB 的容量为 3。

现在，假设找到的第一条路径是 ABCF，其中瓶颈容量为 8。因此，我们在创建此图的路径上推送 8 个流：

现在让我们说下一条路径是 ACBDF。

我的问题是我们现在能够通过 CB 推动多少流量？是 11 通过使用 8 个已经推送的流以及另一边的 3 个容量，还是只有 3 个或可能是 8 个？

感谢您的时间。

我正在学习 Ford-Fulkerson 算法，并且我知道我们需要后向边缘，因为我们选择的增强路径可能对最终的最大流量没有贡献。但我想知道是否存在一系列不需要后向边缘的增广路径？我尝试了很多例子，似乎存在，但我不知道如何证明。