如何使给定的无向图成为双连通图，添加最少的边数？
How a given undirected graph could be made biconnected adding minimum number of edges?
我有一个连接的无向图。如何添加最少数量的边使其成为双连通的？
我试着在网上搜索这个特定的算法，也试着自己思考，但什么也想不出来。伪代码会很棒。谢谢！
搜索 minimum cut：如果等于 2，则很好，如果等于 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，2002 年 10 月，第 55-71 页。作者将他的方法描述为 "very simple"。伪代码如下。
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 等）。既然您有了一些关键字，也许您可以在某处找到一个实现。
我有一个连接的无向图。如何添加最少数量的边使其成为双连通的？
我试着在网上搜索这个特定的算法，也试着自己思考，但什么也想不出来。伪代码会很棒。谢谢！
搜索 minimum cut：如果等于 2，则很好，如果等于 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，2002 年 10 月，第 55-71 页。作者将他的方法描述为 "very simple"。伪代码如下。
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 等）。既然您有了一些关键字，也许您可以在某处找到一个实现。