minimum-cut

1热度

1回答

我刚刚完成coursera中算法专业课程中的第一个模块。有一个考试问题，我不明白。我已通过考试，所以我没有必要重新考试。出于好奇，我想了解围绕这个问题的原则。问题被张贴这样：假定一个随机算法成功（例如，正确地计算的曲线图的最小切）的概率为p（0 < p < 1）。设ε 为小正数（小于1）。运行该算法需要多少次独立时间才能确保至少有1-ε的概率，至少有一次试验成功？给出的选项是：日

0热度

1回答

使用Kruskal算法寻找图的最小切割值

我是一名初学者，我试图用Java中的Kruskal算法找到图的最小切割。我已经到了我可以读取输入的位置，并创建vertexCount^2数量的边缘随机权重的MST。我所要做的就是从我的MST中找出需要多少次切割来分离S和V-S。这将允许我选择vertexCount^2个选项中的最小值。我想我理解正确，我应该忽略MST的最后一个边缘来获得S和V-S。但是我很难弄清楚有多少边连接S和V-S。所以

4热度

1回答

使用Kruskal算法寻找图中的最小切点？

我们已经看到，生成树和切割是密切相关的。这是另一个连接。让我们删除克鲁斯卡尔算法添加到生成树的最后一条边;这将树分成两个部分，从而在图中定义一个切割（S，S）。我们可以说这个削减？假设我们正在使用的图是未加权的，并且它的边是随机排列的，以便Kruskal算法处理它们。这是一个值得注意的事实：在概率至少为1/n^2的情况下，（S，S）是图中的最小切割，其中切割的大小（S，S）是S和S之间的边的数量。

1热度

2回答

查找流网络的最小割

我试图找到下面网络的最小割我使用下面的算法：润福特Fulkerson算法，并考虑最终残差图。找到残差图中可以从源访问的一组顶点。从可到达顶点到不可到达顶点的所有边都是最小切割边。打印所有这些边缘。在第一步骤中，我的算法找到3条路径： - s->b->h->t **value: 1** - s->d->e->t **value: 1** - s->c->h->i->m->d->g->t

4热度

1回答

随机最小切，Karger算法

我正在实施Karger算法。据我所知，最后两个节点之间的边数并不总是最小割。我无法理解的是如何真正从这种算法中获得最小的优势。我一直在寻找很多可能性的东西，但对我来说这一切看起来都很乱... 从我读过的内容中，我想我需要在图上多次运行Karger算法。这会让我很有可能击中最低分。我认为？... 有人可以请简单解释一下吗？我如何找到运行此算法的次数？我刚才所说的正确吗？