3

ここに完全な質問があります：

有向グラフ G = (V,E) があると仮定し、次のプロパティを持つグラフ G' = (V,E') を見つけたいとします。

  1. G' は G と同じ連結要素を持つ
  2. G' は G と同じ成分グラフを持つ
  3. E' は最小化されます。つまり、E' は可能な限り小さくなります。

これが私が得たものです：

まず、強連結成分アルゴリズムを実行します。これで、強連結成分ができました。次に、各強力な接続コンポーネントに移動し、その SCC 内で単純なサイクルを作成します。つまり、繰り返される唯一のノードが開始/終了ノードであるサイクルです。これにより、各 SCC内のエッジが最小限に抑えられます。

ここで、SCC間のエッジを最小化する必要があります。ああ、これを行う方法が思い浮かびません。

私の 2 つの質問は次のとおりです。(1) SCC間のエッジの最小化に関する部分の前のアルゴリズムは正しく聞こえますか? (2) SCC 間のエッジを最小化するにはどうすればよいですか。

(2) については、これは DAG のエッジの数を最小限に抑えることと同等であることがわかっています。(SCC を頂点と考えてください)。しかし、これは私を助けないようです。

4

2 に答える 2

1

  1. 閉じたウォーク (つまり、頂点の繰り返し) を許可する限り、アルゴリズムは正しいようです。適切なサイクルは存在しない可能性があり (たとえば、「8」の形をしたコンポーネント)、それらを見つけるのは NP 困難です。

  2. コンポーネント間のエッジを、それらが接続するコンポーネントの順序付けられたペアによってグループ化し、各グループに 1 つのエッジのみを残すだけで十分であるように思われます。

于 2013-02-19T08:25:39.043 に答える