Python中的最小割算法

在本教程中，我们将学习 Python 的最小割算法。在这里，我们给定一个无向且无权重的图。从这个图中，我们需要找到最小割（将图形分成两部分的边的数量）。输入图可能包含一些平行边。例如，我们考虑下面的例子。在这里，最小割是 2 条边。

上述图的最小割是 {a, d} 或 {b, e}。一个简单的解决方案是使用基于最大流的 s-t 割算法来找到最小割。将每对源视为“s”并将汇视为“t”，然后调用最小 s-t 割算法。它用于查找 s-t 的所有割。每个割都返回 s-t 的最小值。该算法对图的最优时间复杂度为 O(V5)。存在所有可能的 V2 对，并且单对的 s-t 割算法需要 O(V*E) 和 E = O(V2) 时间。

以下是一个简单的 Karger 算法用于此目的。下面的 Karger 算法可以在 O(E) = O(V2) 时间内完成。

1. 收缩图 CG 被初始化为原始图的副本。
2. 当顶点数超过 2 时。
   1. 在收缩图中选择一条随机边 (u, v)。
   2. 将 u 和 v 合并成一个单独的顶点。
   3. 删除自环
3. 将表示从两个顶点切回。

现在，我们通过给定的例子来理解上述算法。首先，我们随机选择了顶点“a”，它连接顶点 0 和 1。我们删除这条边并使图变小（通过合并 0 和 1 顶点）。我们看到下面的图。

现在，下一个随机选择的边是“d”。然后我们删除这条边并将顶点（0,1）和 3 放在一起。

从图中，我们需要移除自环。所以，我们移除边“c”。

图现在有两个顶点，所以我们停止。得到的边数是 Karger 算法造成的割。Karger 算法是一种蒙特卡洛算法，它造成的割不一定是最小的。例如，下图显示了不同顺序的随机选择边会创建一个大小为 3 的最小段。

程序代码

现在，我们给出 Python 中最小割算法的程序代码。输入图表示为边的集合，并且并集查找用于跟踪对象的模型。代码如下：

输出

现在，我们在 Python 中编译上述代码，成功编译后运行它。输出如下：

The Contracting edge is 0-2
The Contracting edge is 0-1
The Contracting edge is 2-3
min cut found by Karger's randomized algo is 0

本文将讨论简单的 Karger 算法，并表明它不需要产生最小割。上述算法以大于或等于 1/(n2) 的概率产生最小割。

上述代码的复杂度分析

上述代码的时间复杂度为 O (EV^2)。这里，E 代表图中的边数，V 代表顶点数。该算法仅保证找到最小割，但通过大量迭代，它有很大机会找到最小割。时间复杂度由运行 V-2 次迭代并在每次迭代中执行固定量工作的循环决定。每次迭代的工作包括折叠元素子集、子集组合和边。因此，时间复杂度为 O (EV^2)，其中 V 是顶点数，E 是边数。

辅助空间 O(E + V) 在上述代码中。E 代表图中的边数，V 代表顶点数。这是因为程序使用了需要 O (E) 空间来存储图的连续列表。它还使用了需要 O(V) 空间来访问的顶点和 BFS 队列。总的来说，这个程序使用 O(E+V) 的辅助空间。

结论

因此，在本教程中，我们正在学习 Python 的最小割算法。我们使用了 Karger 算法来查找无向、连通图中的最小割，并且是无权重的。我们还提供了一个 Python 最小割算法的程序代码，并分享了它的输出。