I have a undirected graph which is connected. How could it be made biconnected adding minimum number of edges?
I tried searching online for this particular algorithm and also tried thinking myself but couldn't figure out anything. Pseudocode would be great. Thanks!
あなたの問題は、双方向接続拡張問題として知られています。計算の複雑さは、グラフのタイプ (エッジ加重、加重なし、有向、無向) によって異なります。無向グラフの場合、O(V+E)これは非常に優れていると思います。ただし、アルゴリズムは非常に複雑なようです。追加のエッジの絶対最小数をあまり気にしない場合は、二重接続されたコンポーネントをかなり簡単に見つけて、各二重接続されたコンポーネントから星の中心を引いたエッジを 1 つ追加するだけです (スター パターンで)。エッジを追加するには、まだいくつかの条件があります。議論については、 http://www.cs.utexas.edu/~vlr/papers/bi_aug.psを参照してください。最新の参考文献が他にもあると確信していますが、この問題の詳細を見つけるのは困難です。
また、Tsan-sheng Hsu による「Simpler and fast biconnectivityaugmentation」という参考文献も見つけました。Journal of Algorithms 45、1、2002 年 10 月、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 など) を知る必要があります。いくつかのキーワードがあるので、おそらくどこかで実装を見つけることができます。
最小カットを検索します。2 に等しい場合は合格です。1 の場合は、カットの 2 つの側面の間にエッジを追加します。すすいで繰り返します。