16

ノードのセットとそれらの間に有向エッジのセットがあります。エッジには重みがありません。

グラフを強力に接続するために追加する必要のあるエッジの最小数を見つけるにはどうすればよいですか（つまり、すべてのノードから他のすべてのノードへのパスが必要です）。この問題には名前がありますか？

4

3 に答える 3

29

これは本当に古典的なグラフの問題です。

  1. Tarjan-SCCアルゴリズムのようなアルゴリズムを実行して、すべてのSCCを検索します。各SCCを新しい頂点と見なし、原点グラフに従ってこれらの新しい頂点間のエッジをリンクすると、新しいグラフを取得できます。明らかに、新しいグラフは有向非巡回グラフ（DAG）です。
  2. DAGで、次数が0のすべての頂点を見つけ、それらを{X}と定義します。アウトディグリーが0であるすべての頂点を見つけ、それらを{Y}と定義します。
  3. DAGに頂点が1つしかない場合、答えは0です。それ以外の場合、答えはmax（| X |、| Y |）です。
于 2013-01-14T12:20:43.450 に答える
1

私の頭のてっぺんから、有向グラフを強く接続するための最も簡単な（最も少ないエッジの）方法は、すべてのノードを含むサイクルを持つことだと思われます。したがって、エッジの最小数はNになります。ここで、Nはノードの数です。すでにエッジがある場合は、完全なサイクルを形成するまで、現在のパスと重ならない次に長いパスに既存の最長の有向パスを接続するなどの操作を行います（パスにすべてのノードが含まれるようになったら、両端を接続してサイクル。）

これのいずれかのより正式な定義があるかどうかはわかりませんが、私には論理的であるように思われます。

于 2013-01-13T16:11:45.173 に答える
1

私はすべての弱く接続されたコンポーネントを見つけて、それらをサイクルで結びます。

編集：

より明確に言うと、WCCがある場合は、の任意のノードからW(1),...,W(n)すべてに到達できるようにするという考え方です。W(i%n + 1)W(i)i=1 to n

于 2013-01-13T19:35:20.103 に答える