问题标签 [minimum-cut]

假设给定一个加权的连通图。我想找到一个可以从图中删除的边列表，将其分成两个组件，以便删除边的权重总和很小。理想情况下，我希望得到最小的总和，但我会接受一个合理的近似值。

这似乎是一个难题。有没有什么好的算法可以做到这一点？

如果有帮助，在我的情况下，节点数约为 50，并且图形可能很密集，因此大多数节点对之间都会有一条边。

我们已经看到生成树和切割是密切相关的。这是另一个连接。让我们删除 Kruskal 算法添加到生成树的最后一条边；这将树分成两个组件，从而在图中定义了一个切割 (S,S)。我们能说什么？假设我们正在处理的图是未加权的，并且它的边是随机均匀排列的，以便 Kruskal 算法处理它们。这是一个值得注意的事实：至少有 1/n^2 的概率，(S,S) 是图中的最小割，其中割的大小 (S, S) 是 S 和 S 之间交叉的边数. 这意味着重复该过程 O(n^2) 次并输出找到的最小切割以高概率产生 G 中的最小切割：用于未加权最小切割的 O(mn^2 log n) 算法。

• 这不取决于通过 Kruskal 算法处理图形的 n^2 种独特方法这一事实吗？我的意思是，如果Kruskal 算法只有3 种独特的方式来处理具有 10 个节点的图，那么重复该过程 n^2 次将不会产生 n^2 独特的“最后一条边”。在唯一的最终切割少于 n^2 个（即少于 n^2 个唯一的“最后边缘”）的情况下，它将如何工作？

• 如果总共有少于 n^2 条边怎么办？例如，您可以有一个只有 9 条边的 10 个节点的连通图，这意味着无论您重复该算法多少次，您都不会有 n^2 个唯一的“最后一条边”。在这种情况下它将如何工作？

• 循环遍历每个边缘并检查边缘是否是最小切割不是更容易吗？在 n 个节点的图中，唯一边的最大数量为 n + n-1 + n-2... + 1 条边，小于 n^2。考虑到 n^2 小于 n^2 log n，为什么不直接遍历所有边，因为这样更快？

给定一个网络 G=(V,E) ，一个最大流 f 和一个 E 中的边 e，我需要找到一个 efficeint 算法来检测是否存在一些包含 e 的最小割。另一个问题是，如果我发现 e 包含在某个最小切割中，是否可以检测它是否是切割中最轻的边缘？

我考虑过运行 Ford-Fulkerson 算法，并增加/减少给定边缘的容量，看看会发生什么，但我还没有想出一些可以帮助我解决问题的方法。

如果有人能指出我的解决方案，我将不胜感激，在此先感谢。

我一直在努力解决这个问题。实际上已经有好几个星期了，但我用完了可能的解决方案或修改。所以该算法是一个随机 Karger 最小切割算法 & 我的实现如下提供：

算法：

它用于无向图。每个顶点都作为键存储在 hashmap 中，其相邻顶点作为 arraylist 存储在 hashmap 的值中，例如

如果测试用例是：

其中第一列是键，与它们相邻的数字是它的值（arraylist）。

我的算法是

1. 选择一个名为“i”的第一个出现的顶点，它有两个以上的相邻顶点（在本例中为 2 个）
2. 虽然“i”的列表中有两个以上的数字
3. 随机选择一个相邻的顶点，称为“U”
4. 将“U”与“i”合并（将其与另一个名为“V”的顶点合并不会给出正确答案）
5. 现在检查新的“i”列表是否包含“i”本身并将其删除。（自循环）
6. 将新的“i”列表交叉引用到其他顶点

7. 删除“U”（键），例如如果“U”为 6，则更新的顶点如下所示：

   /li>

8. 因此，当“i”将具有唯一编号时，算法将终止（通过将“i”的列表添加到 Set 来完成）。例如：

   /li>

所以这是给定图的 2 个最小切割。

代码：

我在java中的上述算法的代码如下：

问题：

我面临的问题是，除了一个由 200 个顶点组成的非常大的测试用例之外，该算法几乎适用于我遇到的所有测试用例。正确的答案应该是 17，但我继续得到我的答案为“20”。我跟踪了所有选择的“U”。显然它们都是独一无二的，没有任何重复，我不断得到答案“20”。请问有什么建议吗？再次感谢。测试用例的链接是：

http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt

注意：

这不是家庭作业，而是我在 coursera 的在线课程（算法设计和分析）中看到的一个练习题。现在课程结束了。非常感谢您提前。我再次问这个问题，因为我第一次无法得到答案。我将不胜感激提供的任何帮助，因为我说这个问题对我造成了影响，因为我已经研究了很长时间。

令 (G,s,t,{c}) 为流网络，令 F 为所有边 e 的集合，其中至少存在一个最小割 (A,B)，使得 e 从 A 到 B。给出一个多项式时间算法，找出 F 中的所有边。

注意：到目前为止，我知道我需要运行 Ford-Fulkerson，以便每个边缘都有一个流程。此外，我知道对于 F 中的所有边，流 f(e) = c(e)。然而，图 G 中并非所有尊重该约束的边都将处于最小切割中。我被困在这里。

我正在实施 Karger 的算法。据我了解，最后两个节点之间的边数并不总是最小切。我难以理解的是我如何真正从这个算法中得到最小切分。我一直在寻找很多关于概率的东西，但对我来说这一切都像是胡言乱语......

根据我的阅读，我认为我需要在图表上多次运行 Karger 算法。这将使我很有可能成功击中最小切线。我认为？...

有人可以用更简单的方式解释一下吗？如何找到运行此算法的次数？我上面所说的是否正确？

我一直在努力弄清楚如何做到这一点。我有兴趣快速找到图形的割集。我知道 BGL 支持通过对例如 edmonds_karp_max_flow 支持的 colorMap 参数进行迭代来查找割集。Gomory Hu 算法需要多次调用最小割算法。

我希望的结果是拥有一个包含以下内容的多图：（颜色，顶点）

以下代码尝试重写 Boost Graph Library 中的示例，以使用多映射作为 associative_property_map。可以使用以下命令编译代码：clang -lboost_graph -o edmonds_karp edmonds_karp.cpp 或 g++ 而不是 clang。我不明白出现的错误。

提示将不胜感激。谢谢你。

我正在尝试从 Vladimir Kolmogorov 的优秀 Graph cut library 中理解一些代码，并且我有一个关于图形构造的问题。假设我有一个二进制变量系统，我需要表示以下削减成本

此外，假设这些能量是：

两个变量是 x 和 y，源节点和汇节点由 s 和 t 表示：

现在，正如我在 E(0, 0) 中看到的那样，我需要一条从 x 到 t 和从 y 到 t 的边。它们的容量为 A。因此，如果这两条边都被切割，则 x 和 y 都属于源节点（与标签 0 相关联）。所以像：

现在对于 E(0, 1)，我需要另一个从 s 到 y 的边也具有容量 A，所以现在 Graph 看起来像：

现在我的问题是，由于 s->y 的容量为 A，而 y->t 的容量为 A，我可以在不更改此图上的最小切割的情况下删除这两条边吗？我问的原因是这种结构确实是由从 x 到 t 的一条边给出的（在 Kolmogorov 库的源代码中），我无法理解这种结构。

基于图的方法已被用于医学图像分割问题。图像中的每个像素（3D 中的体素）由图中的一个节点表示，而边连接相邻节点。此外，还增加了两个节点，即源和汇。为每个节点（源和汇除外）定义一个成本，基于该成本计算最小成本闭合集。该集合对应于将属于源的节点与属于汇的节点分开的边界（3D 中的表面）。通常这个边界给出了所需的分割。详细信息在本文中。

我已经看到很多使用这种方法的作品，但有些人称他们的方法为图搜索（Garvin 等人），而另一些人称他们的方法是图切割（Kaba 等人）。阅读后，这些作品看起来非常相似。

还有另一项工作暗示了图形搜索和图形切割之间的区别，但即使在阅读了这项工作之后，我也无法理解其中的区别。

如果有的话，有人可以澄清一下区别吗？

问题如下：给定一个 DAG 和一个 number 0 < p ≤ 1，返回最小基数的顶点集合，它至少断开p从源（即，没有传入弧）到汇（即，没有传出弧）的路径的一部分）。对于p = 1，问题等价于最小割。但是，对于 的其他值p，我不确定答案是什么。

我正在考虑的一种算法是首先计算 DAG 的最小割集，然后尝试对其进行修剪以满足标准。这本身很有趣，看看我们找到的子集是否实际上p是给定特定的最小割集。该算法的问题在于它是浪费的，因为它计算了许多我们在最终答案中不需要的节点，实际上，它首先解决了“更大”的问题。

任何指向这个问题的解决方案？对于某些最小切算法，我们是否可能将这个额外的约束作为提前停止的标准？

为了检查有多少路径被删除，假设我们已经为每个顶点建立了索引（如果需要，会保持更新），这样我们就知道有多少路径因为它们的删除而断开连接。请不要担心正在更新的索引的复杂性。最后一件事，在大小或任何方面对生成的组件没有任何限制。