有向非巡回グラフから強連結成分を作成しようとしています。
入力はフォーム内のエッジのリストです
1 2
3 5
etc
強く接続されたコンポーネントのグラフを作成するために、指定されたグラフに追加されるエッジの最小セットのアウトポイントを作成する必要があります....
何か案は？
これが私が探しているものの例です：
入力が与えられた場合:
1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9
出力は、強く連結されたコンポーネントを作成するために加算に必要なエッジの最小数になります。
出力：
3 1
4 5
7 6
8 1
9 2
グラフに孤立した頂点がないと仮定すると、max(|sources|,|sinks|) 個のエッジを追加するだけで強く接続できます。
T={t 1 ,…,t n } を DAG のシンクとし、{s 1 ,…,s m } を DAG のソースとする。n <= m とします。(他のケースも非常に似ています)。次のように定義された 2 つのセット間の 2 部グラフ G(T,S) を考えます。G(T,S) がエッジ (t i ,s j ) を持つのは、s jから t iに到達できる場合のみです。
M を G(T,S) の最大マッチングとする。一般性を失うことなく、M が k 個のエッジで構成されると仮定します: {(t 1 ,s 1 ),(t 2 ,s 2 ),…,(t k ,s k )}。元のグラフ DAG G に、有向辺 {(t 1 ->s 2 ),(t 2 ->s 3 ),…,(t k−1 ->s k ),(t k ->s 1 )}。これらのエッジを追加することで、M によって誘導された頂点が G で強く接続されていることが簡単にわかります。
ここで、G(T,S) の残りの頂点を考えます。M が最大であるため、S-M (それぞれ T-M) の各頂点は T (それぞれ S-M) の頂点に接続する必要があります。したがって、残りの頂点を任意にペアにし、たとえば {(t k+1 ,s k+1 ),…,(t n ,s n )} とし、対応する有向辺を G に追加します。残りのソース頂点ごとにソース s i (i は {n+1,…,m} に属します。G にエッジ (t 1 ->s i ) を追加します。したがって、追加されるエッジの総数は max(|sources|,|sinks|) です。
編集:いくつかの例を追加する
入力の例について。最初に最大マッチングを計算します。たとえば、次のようにします。
3--1
4--2
7--5
8--6
したがって、エッジを追加します。
3->2
4->5
7->6
8->1
マッチングに存在しない残りの (シンク) 頂点は 9 であるため、9 からの弧をマッチングの任意のソース頂点に追加します9->1。
アルゴリズムのすべてのステップを示す別の例を次に示します。
入力グラフ:
12 3 5 9 10 (sources)
\|/ /|\ \/
4 6 7 8 11 (sinks)
最大マッチング:
4--1
6--5
11--9
したがって、エッジを追加します。
4->5
6->9
11->1
現在、残りのシンクは{7, 8}であり、残りのソースは{2, 3, 10}です。任意に 7 を 2 と、8 を 3 とペアにして追加します。
7->2
8->3
最後に、残りの (ソース) 頂点は 10 であり、以下を追加します。
4->10
私があなたの質問を正しく理解していれば、グラフの隣接行列表現を使用する必要があります。最初は、1 を含むスパース マトリックスか、現在のエッジがある場所になります。
マトリックスの単純なトラバーサルを使用して、SCC を作成するために必要なすべての 0 要素 -> 1、およびそれらの変換のそれぞれが、追加する必要があるエッジになります。
これに使用される可能性のある一般的なアルゴリズムを示す優れた wiki ページもあります。