3

在用于无向（可能加权）多重图的Karger 最小割算法中，主要操作是收缩随机选择的边并将其事件顶点合并到一个元顶点中。重复这个过程，直到剩下两个顶点。这些顶点对应于一个切割。该算法可以使用邻接列表来实现。

问题：

  1. 我怎样才能找到已选择收缩的特定边缘？

  2. 边缘如何收缩（在未加权和/或加权图中）？

  3. 为什么这个过程需要二次时间？

编辑：我发现一些信息表明运行时间可以是二次的，因为我们有 O(n-2) 个顶点收缩并且每次收缩可能需要 O(n) 时间。如果有人能解释一下，为什么收缩在邻接列表中需要线性时间，那就太好了。注意收缩包括：删除一个相邻边，将两个顶点合并为一个超节点，并确保剩余的相邻边连接到超节点。

伪代码：

procedure contract(G=(V,E)):
while |V|>2
    choose edge uniformly at random
    contract its endpoints
    delete self loops
return cut

我已阅读相关主题Karger Min cut algorithm running time，但对我没有帮助。另外我没有太多经验，因此非常感谢“外行”术语解释！

4

0 回答 0