3

問題：ツリーT =（V、E）が与えられます。新しく作成されたグラフから1つのエッジが削除されても、任意の頂点から他の頂点へのパスが存在するように、最小数のエッジを追加します。

問題は、グラフの最小カットのサイズを現在の最小カットの1から2に増やすことで軽減できると思います。しかし、そうするための効率的なアルゴリズムは何でしょうか。

4

2 に答える 2

2

これがアルゴリズムであり、無向グラフのこの問題を解決します。いくつかの簡略化の後、ツリーに適用できます（ステップ1は必要ありません）。

  1. DFSまたはRobertTarjanによるブリッジ検索アルゴリズムを使用して、グラフ内のすべてのブリッジを検索します。
  2. グラフ（実際にはツリー）を作成します。ここで、各ブリッジレスサブグラフが単一の頂点に置き換えられます。
  3. ツリー内のすべてのチェーンを1つのエッジに折りたたむ。
  4. 2つの葉の間のパスを見つけます（可能な場合は少なくとも3つの長さ）。
  5. このパスの両端に対応する、元のグラフのサブグラフ内の任意の2つの頂点を選択し、それらを接続します。
  6. このパスを単一の頂点に折りたたむ。
  7. ツリーに複数の頂点がありますが、手順3から繰り返します。

ステップ4は、最適化の鍵となるステップ6の後に新しい不要なリーフを取得しないことを保証します。

于 2012-10-06T09:14:18.450 に答える
1

Evgenyのソリューションは非常に優れていますが、Treesで機能し、その正確性を簡単に確認できる、より単純なソリューションを次に示します。

L木の（元の）葉になりましょうT。n削除によって取得された各サブツリーが最大で元の葉を持つように、ツリー内の任意のノードとしnます|L|/2。そのようなノードを見つけることは常に可能であることに注意してくださいn。

1、2 、..、Tkを、。を削除して取得したサブツリーとします。すべての元の葉（in ）は、iの1つに存在します。任意のペアの2つの元の葉が別個のサブツリーに属するという制約の下で、元の葉から最大の互いに素なペアを構築します。（これは、部分がサブツリーに存在する元の葉である完全なk-partiteグラフで最大マッチングを構築することと概念的に同じです）。TTnLT

偶数の場合|L|、すべての元の葉がいくつかのペアに存在し、これらのペアのそれぞれに対応するエッジを追加すると、結果のグラフが2接続されます。|L|/2したがって、この場合はエッジを追加する必要があります。

奇数の場合|L|、1つの元のリーフはペアにならないため、このリーフを別のサブツリーに存在する任意の元のリーフに接続できます。この場合、(|L|+1)/2エッジを追加する必要があります。

于 2012-10-06T16:20:08.760 に答える