问题标签 [minimum-cut]

我是一名初学者，我正在尝试使用 Java 中的 Kruskal 算法找到图形的最小分割。

我已经到了可以读取输入并为边缘创建随机权重的 vertexCount^2 数量的 MST 的位置。我剩下要做的就是从我的 MST 中计算出分离 S 和 VS 需要多少次削减。这将允许我从 vertexCount^2 个选项中选择最小值。

我想我理解正确，我应该忽略 MST 的最后一条边来获得 S 和 VS。但是我不知道如何弄清楚有多少条边连接了 S 和 VS。

所以我的问题是：1）vertexCount^2 随机 MST 是否足以确信它将包含最小切割？2) 我怎样才能找到连接 S 和 VS 的边数？

PS。这是我的代码的一个片段：

PSS。如果这是相关的，我在编写代码时查看了来自http://algs4.cs.princeton.edu/43mst/的代码。

这是一个询问图的边缘连通性与其最小切割之间的联系的问题。

众所周知，无向图的边连通性是k为断开图而必须移除的最小边数。例如，树的边连通性为 1，环的边连通性为 2。

我的想法是最小切割的容量应该等于边缘连接。因为割就是把一个图分成两个不连贯的部分。如果我们知道边的连通性k，则意味着我们必须至少删除或切断k边才能使图分成两个不连贯的部分。因此最小切割的容量应该是k。

我还没有找到关于这个问题的任何结论或证据，所以我在这里问。谁能检查我的想法是否正确或给我任何其他想法？

我有一个图 G，它是一个有向且强连通的图，我被要求找到所有顶点对的最小割，这意味着图中的每一对 S 和 T。这应该在 O(m ² × n ² ) 时间内完成。

我想出的最好的方法是将所有顶点视为 S，并且对于每个 S，将所有其他顶点视为 T，并且对每个顶点运行 Ford-Fulkerson 算法，然后找到最小割。但如果我没记错的话，这个算法的复杂度是 O(m ² × n ² × C)。

我怎样才能在 O(m ² × n ² ) 时间内完成这项任务？甚至可能吗？

我有一个无向加权图，我需要找到分隔两组顶点的最小割。我可以修改我的设置，以减少找到分隔两个给定顶点的最小切割的问题。我想补充一点，权重是正数和分数。

Stoer-Wagner 算法除了将指定节点保留在切口的不同侧之外，什么都做，我很好奇是否有任何方法可以修改 SW 来做到这一点。

谢谢你。

所以我计算出最大流量为 10，因此意味着最小切割也为 10，但是我如何在此图像上绘制最小切割 10？

是否有任何算法或代码将图节点划分为两个或多个满足以下条件的不相交集：首先，只允许删除边。其次，对边缘进行加权，并且那些将被删除的边缘必须具有最小权重（最小切割算法）。第三，期望的不相交集尽可能长。

给定一个通常包含许多奇数和偶数循环的无向加权图（或更大的不相交图的单个连通分量），我正在寻找算法来删除尽可能少的边数，以便生成一个或多个二分子图. 文献中是否有任何标准算法，例如存在最小切割等？

我试图解决的问题在现实世界中是这样的：在一个或两个时间段内向学生提供关于不同主题的每个大约 1 小时的演示。学生可以注册至少一个他们选择的演示文稿，或者两个，或三个（第 3 选择是一个替代方案，以防其他一个不会出现）。它们必须是不同的选择。如果给定演示文稿的注册人数少于三个，则不会给予。如果有 18 个或更多，它将在两个块中给出两次。我必须安排演示文稿，以便满足最大数量的注册。

在以下情况下，调度是微不足道的：

1. 如果提供演示文稿，则始终可以满足仅一个演示文稿的注册（即注册数> = 3）；

2. 如果至少其中一个被给予两次，那么两次给定演示文稿的注册总是令人满意的。

首先，汇总所有注册，以确定哪些注册一次，哪些注册两次。如果学生已报名参加其他报名人数太少的演示文稿，则选择替代演示文稿（如果它也将提供）。

归根结底，我得到了一个无向加权图，其中顶点是演示文稿，边代表已注册该演示文稿组合的学生，每个演示文稿只呈现一次。权重对应于独特演示组合的注册数量（从而避免平行边）。

如果顶点或表示的数量约为 20 或更少，我想出了一个在可接受的时间内完成的蛮力解决方案。但是，每个额外的顶点都会使该解决方案的运行时间加倍。在 28 岁左右之后，它迅速变得无法控制。

今年我们进行了 37 次演示，其中 30 次只进行了一次，因此最终出现在图表中。我现在正在尝试更大的图表如下：

1. 找到所有分立元件并单独求解每个元件；
2. 对于每个组件，递归地移除叶子节点和桥接边；
3. 生成一棵生成树（我正在使用运行良好的 Kruskal 算法），保存删除的边缘；
4. 通过一次将一个删除的边缘添加回树并剥离树的其余部分来生成基本循环集；
5. 使用 Gibbs-Welch 算法，我从步骤 4 中获得的基本集合开始生成所有元素循环的完整集合；
6. 统计每条边所属的奇偶周期数；
7. 创建边的优先级队列（下面讨论排序）并从其连接的组件中连续删除每个边，直到结果组件是二分的。

我找不到优先级队列的排序，我可以证明其结果与使用蛮力方法获得的解决方案一样可接受（它可能是 NP-hard）。但是，我正在尝试这些方面的东西：

一种。如果边只属于奇循环，先去掉；

湾。如果边属于奇数多于偶数循环，则在任何其他属于偶数多于奇数的边之前将其删除；

C。应首先删除权重最小的边缘。

如果一条边同时属于奇数和偶数循环，则删除它会留下更大的奇数循环。这就是为什么我要这样订购它们。显然，边缘所属的奇数周期数越大，优先级越高，但前提是影响的偶数周期越少。

还有其他标准存在，但需要在图形问题之外考虑；例如，删除边缘有效地删除了其中一个演示文稿的注册，因此必须注意不要让注册的数量变得太少。

（编辑：也有可能将演示文稿分成两个几乎有足够注册的块，例如 15-16 而不是 18。但这意味着进行演示的人必须做两次，所以这是一个权衡。）

在此先感谢您的任何建议！

我刚刚完成了 coursera 算法专业课程的第一个模块。

有一个考试题，我不太明白。我已经通过了那次考试，所以我没有重考的意义。

出于好奇，我想了解围绕这个问题的原则。

问题是这样发布的：

假设随机算法以概率 p（0 < p < 1）成功（例如，正确计算图的最小割）。设 ϵ 是一个小的正数（小于 1）。

您需要多少次独立运行该算法才能确保以至少 1-ε 的概率至少有一次试验成功？

给出的选项是：

log(1−p)/logϵ

对数（p）/对数ε

对数ε/log(p)

logϵ/log(1−p)

我做了两次尝试，都错了。我的尝试是：

1. log(1−p)/logϵ
2. logϵ/log(1−p)

我不是很想知道正确的答案。我想了解这个问题背后的原则以及它的要求。这样我就知道将来如何回答类似的问题。

我在论坛上发了这个，但一个月后没有人回复。所以我在这里尝试一下。

无需直接发布答案。如果你让我明白了，我会把它标记为正确的。

谢谢。

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

我正在使用以下算法：

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

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

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

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

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

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

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

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

我一直在阅读一些关于分割图结构的多重算法的论文。我对这项工作特别感兴趣，它提出了一种算法来解决多切问题的扩展：

https://www.cv-foundation.org/openaccess/content_iccv_2015/papers/Keuper_Efficient_Decomposition_of_ICCV_2015_paper.pdf

关于边缘成本，它说：

...对于任何一对节点，这些节点位于不同组件中的所有分解的实值成本（奖励）

很公平。它进一步说，多割问题的解决方案是一个简单的二进制向量，其长度等于图中的边数，其中“1”表示相应的边将两个属于不同图组件的顶点分开：

对于每条边 vw ∈ E ∪ F ，当且仅当 v 和 w 在 G 的不同分量中时，y(v,w) = 1。

但是优化问题写成：

这似乎没有意义。如果边权重描述了在不同组件中连接节点的边的奖励，这不应该是一个最大化问题吗？在任何一种情况下，如果所有边权重都是正的，那不会导致一个简单的解决方案，其中y全零向量是什么？上面的表达式后面是论文中的一些约束，但我不知道其中任何一个是如何阻止这种结果的。

此外，当它稍后尝试使用贪婪加性边缘收缩生成初始解决方案时，它说：

阿尔格。1 从分解为单个节点开始。在每次迭代中，连接一对相邻组件，该连接最大程度地降低了目标值。如果没有连接严格减少目标值，则算法终止。

同样，如果边权重是保持节点分离的奖励，那么加入任何两个节点不会减少奖励吗？即使我假设边缘权重是保持节点分离的惩罚，这种方法不会简单地将所有节点集中到一个组件中吗？

我看到这可行的唯一方法是边缘权重是正值和负值的平衡组合，但我很确定我错过了一些东西，因为文献中没有提到这个约束。