undirected-graph - 如何使给定的无向图成为双连接添加最小边数？

Question

我有一个连接的无向图。如何使它成为双连接添加最小数量的边？

我试着在网上搜索这个特定的算法，也试着自己思考，但什么也想不通。伪代码会很棒。谢谢！

Answer 1

您的问题被称为双连通性增强问题。计算复杂度根据图的类型（边加权、未加权、有向、无向）而有所不同。我相信对于无向图来说，O(V+E)这非常好。然而，该算法似乎相当复杂。如果您并不真正关心附加边的绝对最小数量，您可以相当容易地找到双连通分量，只需为每个双连通分量添加一个额外的边（比如以星形图案）减去星形的中心。添加边还有一些条件。有关讨论，请参见http://www.cs.utexas.edu/~vlr/papers/bi_aug.ps。我确信有更多最新的参考资料，但很难找到这个问题的详细信息。

我还找到了 Tsan-sheng Hsu 的参考“Simpler and faster biconnectivity augmentation”，Journal of Algorithms 45, 1, October 2002, pages 55-71。作者将他的方法描述为“非常简单”。伪代码如下。

Input: A graph G = (V , E);
Output: A smallest set of edges aug2(G) such that G ∪ aug2(G) is biconnected;
1. If G has less than 3 vertices or is biconnected, then return ∅.
2. If G is disconnected, then apply Fact 3.2 to find a set of edges E1 such that G ∪ E1 is connected;
otherwise, let E1 = ∅.
3. Find a vertex r in blk2(G ∪ E1) such that blk2(G ∪ E1) rooted at r is normalized.
4. If r is a b-node, then do the following:
(a) Apply Lemma 3.4 on G ∪ E1 to find a set of edges E2.
(b) Return E1 ∪ E2.
5. If r is a c-node, then do the following:
(a) If G ∪ E1 is not balanced, then apply Fact 3.6 on G ∪ E1 to find a set of edges E3 such that
G ∪ E1 ∪ E3 is balanced; otherwise, let E3 = ∅.
(b) Root blk2(G ∪ E1 ∪ E3) at r.
(c) Apply Lemma 3.9 on G ∪ E1 ∪ E3 to find a set of edges E4.
(d) Return E1 ∪ E3 ∪ E4.

遗憾的是，为了使用它，您需要了解所有定义（b-node、c-node、blk2、Fact 3.6 等）。既然您有一些关键字，也许您可​​以在某个地方找到一个实现。

Answer 2

搜索最小切口：如果它等于 2，那么你很好，如果它是 1 - 在切口的两侧之间添加一条边。冲洗并重复。