11

重み付きエッジを持つ有向グラフが与えられた場合、最小の重みを持つサブグラフを与えるためにどのアルゴリズムを使用できますが、グラフ内の任意の頂点から他の頂点への移動が可能です（任意の2つの頂点間のパスが常に存在するという仮定の下で） 。

そのようなアルゴリズムは存在しますか？

4

5 に答える 5

3

彼らは自分自身が正しくなかったとしても、時間をかけてVitaliiのウィキペディアのリンクをたどると、このアルゴリズムがすぐに明らかになりました。

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm

于 2010-05-10T07:32:20.563 に答える
2

グラフ内のすべてのノードを2つのノードに分割します。一方のノードは元のノードへのすべての入力エッジを受け入れ、もう一方のノードはすべての出力エッジを受け入れます。次に、すべてのエッジに方向をドロップして、グラフが無向になるようにします。次に、グラフ（Prim、Kruskal）で標準のMSTアルゴリズムを実行し、すべての元のノードが他のすべての元のノードから移動できるようにします。

于 2010-05-11T08:20:34.543 に答える
2

これはNP困難のように見えます：最小重みが強く接続されたスパンサブグラフの問題。

ハミルトン閉路問題はそれに還元できると思います。グラフG（V、E）が与えられた場合、出現するエッジの重みが1、出現しないエッジの重みが100（| V | +1）の有向グラフDGを作成します。DGには、正確に|V|の重みのサブグラフにまたがって強く接続された最小の重みがあります。Gがハミルトン閉路を持っている場合に限ります。

ここの論文には近似アルゴリズムがあります：http：//portal.acm.org/citation.cfm？id = 844363

于 2010-05-19T14:57:31.893 に答える
1

これは、DirectedSteinerTreeの問題です。シュタイナー木として、それはNP困難です。

ここでいくつかの近似アルゴリズムを見つけることができます：

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps

于 2010-08-31T14:05:14.753 に答える
0

任意のノードを選択して返します。

強く接続された最大のサブグラフ（削除されるノードの数が可能な限り少ない）、または最小の重みのスパンサブグラフ（ノードの削除は許可されない）を見つけることを意味しましたか？

于 2010-05-19T19:37:55.263 に答える