強連結成分

有向グラフの数学理論では、グラフは、すべての頂点が他のすべての頂点から到達可能である場合に強連結であると言われます。有向グラフの強連結成分は、それ自体が強連結である部分グラフへの分割を形成します。グラフの強連結性をテストしたり、その強連結成分を見つけたりすることは、線形時間（つまり、Θ( V + E )）で可能です。

定義

有向グラフは、グラフの任意の頂点ペア間に各方向のパスが存在する場合、強連結であると呼ばれます。つまり、ペアの最初の頂点から2番目の頂点へのパスが存在し、2番目の頂点から最初の頂点へのパスも存在します。強連結でない場合もある有向グラフGにおいて、頂点ペアuとvの間に各方向のパスが存在する場合、それらの頂点は互いに強連結であると言われます。

強連結であるという二項関係は同値関係であり、その同値類から誘導される部分グラフは強連結成分と呼ばれる。言い換えれば、有向グラフGの強連結成分とは、強連結であり、かつこの性質において極大である部分グラフのことである。つまり、Gから追加のエッジまたは頂点の集合を部分グラフに含めると、強連結であるという性質が損なわれる。強連結成分の集合は、Gの頂点集合の分割を形成する。強連結成分Cは、 C がエッジで自身に接続されていない単一の頂点から構成されている場合、自明であるといい、そうでない場合は非自明であるといい。^[¹^]

各強連結成分を単一の頂点に縮約すると、結果として得られるグラフは有向非巡回グラフ、すなわちGの縮約となります。有向グラフが非巡回グラフとなるのは、複数の頂点を持つ強連結部分グラフが存在しない場合に限ります。これは、有向サイクルは強連結であり、自明でないすべての強連結成分には少なくとも1つの有向サイクルが含まれるためです。

アルゴリズム

DFSベースの線形時間アルゴリズム

深さ優先探索に基づくいくつかのアルゴリズムは、強連結成分を線形時間で計算する。

コサラジュのアルゴリズムは、深さ優先探索を 2 回実行します。最初のパスは元のグラフで実行され、2 回目の深さ優先探索の外側のループが頂点が既に訪問されているかどうかをテストし、訪問されていない場合は再帰的に探索する順序を選択するために使用されます。2 回目の深さ優先探索は元のグラフの転置グラフで実行され、再帰的探索ごとに 1 つの新しい強連結成分が見つかります。 ^{[ 2 ]}^{[ 3 ]}このアルゴリズムは、1978 年にこのアルゴリズムを記述した (ただし結果を公表しなかった) S. ラオ・コサラジュにちなんで名付けられ、後にミカ・シャリルが1981 年に発表しました。^{[ 4 ]}
1972年にロバート・タージャンによって発表されたタージャンの強連結成分アルゴリズム^{[ 5 ]}は、深さ優先探索を1回実行します。探索によって探索されたものの、まだ成分に割り当てられていない頂点のスタックを保持し、各頂点の「低い数」（その頂点の子孫から1ステップで到達可能な最高位の祖先のインデックス番号）を計算します。この低い数を使用して、頂点のセットをスタックからポップして新しい成分にするかどうかを決定します。
パスベースの強力コンポーネントアルゴリズムは、タージャンのアルゴリズムと同様に深さ優先探索を使用しますが、2 つのスタックを使用します。一方のスタックは、まだコンポーネントに割り当てられていない頂点を追跡するために使用され、もう一方のスタックは、深さ優先探索ツリー内の現在のパスを追跡します。このアルゴリズムの最初の線形時間バージョンは、1976 年にEdsger W. Dijkstraによって発表されました。 ^{[ 6 ]}

コサラジュのアルゴリズムは概念的には単純だが、タージャンのアルゴリズムとパスベースのアルゴリズムは、深さ優先探索を2回ではなく1回しか必要としない。

到達可能性に基づくアルゴリズム

従来の線形時間アルゴリズムは、一般的に並列化が難しいとされる深さ優先探索に基づいています。Fleischer ら^{[ 7 ]}は 2000 年に、到達可能性クエリに基づく分割統治法を提案し、このようなアルゴリズムは通常、到達可能性ベースの SCC アルゴリズムと呼ばれます。このアプローチの考え方は、ランダムなピボット頂点を選択し、この頂点から前方および後方の到達可能性クエリを適用することです。2 つのクエリは、頂点セットを 4 つのサブセットに分割します。つまり、両方の検索で到達した頂点、どちらか一方のみで到達した頂点、またはどちらの検索でも到達しなかった頂点です。いずれかのサブセットに強連結成分が含まれている必要があることが示せます。両方の検索で到達した頂点のサブセットは強連結成分を形成し、アルゴリズムはその後、他の 3 つのサブセットに対して再帰的に実行されます。

このアルゴリズムの期待される逐次実行時間は O( n log n ) であることが示されており、これは従来のアルゴリズムよりもO(log n ) 倍多い。並列性は、(1) 到達可能性クエリをより簡単に並列化できること (例えば、幅優先探索(BFS) によって、グラフの直径が小さい場合は高速になる)、および (2) 分割統治プロセスにおけるサブタスク間の独立性から生じる。このアルゴリズムは実世界のグラフで良好なパフォーマンスを発揮するが^[³^]、並列性に関する理論的な保証はない (グラフにエッジがない場合、アルゴリズムは O( n ) レベルの再帰を必要とすることを考慮)。

Blelloch ら^{[ 8 ]}は 2016 年に、到達可能性クエリをランダムな順序で適用した場合でも、O( n log n ) のコスト上限が依然として成り立つことを示しました。さらに、クエリはプレフィックス倍増方式 (つまり 1、2、4、8 クエリ) でバッチ処理され、1 ラウンドで同時に実行できます。このアルゴリズムの全体的なスパンは log ₂n の到達可能性クエリであり、これはおそらく到達可能性ベースのアプローチを使用して達成できる最適な並列処理です。

ランダムな強連結グラフを生成する

Peter M. Maurer は、強連結グラフを生成するためのランダムなアルゴリズムについて説明しています。^{[ 9 ]}これは、グラフを強連結にするためにできるだけ少ないエッジを追加する問題である強連結性拡張アルゴリズムの修正に基づいています。ノードの再ラベル付けを伴う Gilbert モデルまたは Erdős-Rényi モデルと組み合わせて使用すると、このアルゴリズムは、生成できる構造の種類に制限なく、n個のノードを持つ任意の強連結グラフを生成することができます。

アプリケーション

強連結成分を見つけるアルゴリズムは、2-充足可能性問題（変数ペアの値に制約があるブール変数のシステム）を解決するために使用できます。Aspvall 、Plass 、 Tarjan（1979）が示したように、2-充足可能性インスタンスは、vとその否定の両方がインスタンスの含意グラフの同じ強連結成分に含まれるような変数vが存在する場合に限り充足不可能になります。^[¹⁰^]

強く連結した成分は、二部グラフのエッジがグラフ内で完全マッチングの一部になり得るかどうかに基づいてエッジを分類するダルマージ・メンデルソン分解を計算するためにも使用されます。 ^[¹¹^]

参考文献

↑ Nuutila, Esko; Soisalon-Soininen, Eljas (1994), "有向グラフにおける強連結成分の発見について", Information Processing Letters , 49 (1): 9–14 , doi : 10.1016/0020-0190(94)90047-7
↑ Thomas H. Cormen、 Charles E. Leiserson、 Ronald L. Rivest、 Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、2001年。ISBN 0-262-03293-7 第22.5節、 552 ～ 557ページ。
1 2 Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013)、「スモールワールドグラフにおける強連結成分（SCC）の高速並列検出について」（PDF）、高性能コンピューティング、ネットワーキング、ストレージ、分析に関する国際会議（SC '13）議事録、 pp. 1–11、doi : 10.1145/2503210.2503246、ISBN 9781450323789S2CID 2156324
↑ Sharir, Micha (1981), "A strong-connectivity algorithm and its applications in data flow analysis", Computers & Mathematics with Applications , 7 : 67–72 , doi : 10.1016/0898-1221(81)90008-0
↑ Tarjan, RE (1972), "深さ優先探索と線形グラフアルゴリズム", SIAM Journal on Computing , 1 (2): 146–160 , doi : 10.1137/0201010 , S2CID 16467262
↑エドガー・ダイクストラ(1976)『プログラミングの規律』ニュージャージー州：プレンティス・ホール、第25章。
↑ Fleischer, Lisa K.; Hendrickson, Bruce; Pınar, Ali (2000), "On Identifying Strongly Connected Components in Parallel" (PDF) , Parallel and Distributed Processing , Lecture Notes in Computer Science, vol. 1800, pp. 505–511 , doi : 10.1007/3-540-45591-4_68 , ISBN 978-3-540-67442-9
↑ Blelloch, Guy E.; Gu, Yan; Shun, Julian; Sun, Yihan (2016), "Parallelism in Randomized Incremental Algorithms" (PDF) , Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '16 , pp. 467– 478, arXiv : 1810.05303 , doi : 10.1145/2935764.2935766 , hdl : 1721.1/146176 , ISBN 9781450342100。
↑ Maurer, PM (2018年2月)、強く連結したランダムグラフの生成(PDF)、国際モデリング・シミュレーション・可視化手法会議 MSV'17、CSREA Press、ISBN 978-1-60132-465-8（ 2019年12月27日取得）
↑ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "特定の量化ブール式の真偽をテストするための線形時間アルゴリズム", Information Processing Letters , 8 (3): 121–123 , doi : 10.1016/0020-0190(79)90002-4。
↑ Dulmage, AL & Mendelsohn, NS (1958), "二部グラフの被覆", Can. J. Math. , 10 : 517– 534, doi : 10.4153/cjm-1958-052-0 , S2CID 123363425 。
↑ Robbins, HE (1939)、「グラフに関する定理、交通管制の問題への応用」、American Mathematical Monthly、46 (5): 281–283、doi : 10.2307/2303897、JSTOR 2303897 。

外部リンク

jBPTライブラリにおける強連結成分の計算のためのJava実装（StronglyConnectedComponentsクラスを参照）。
強連結成分のC++実装

[1] Nuutila, Esko; Soisalon-Soininen, Eljas (1994), "有向グラフにおける強連結成分の発見について", Information Processing Letters , 49 (1): 9–14 , doi : 10.1016/0020-0190(94)90047-7

[2] Thomas H. Cormen、 Charles E. Leiserson、 Ronald L. Rivest、 Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、2001年。ISBN 0-262-03293-7 第22.5節、 552 ～ 557ページ。

[hong2013fast-3] 1 2 Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013)、「スモールワールドグラフにおける強連結成分（SCC）の高速並列検出について」（PDF）、高性能コンピューティング、ネットワーキング、ストレージ、分析に関する国際会議（SC '13）議事録、 pp. 1–11、doi : 10.1145/2503210.2503246、ISBN 9781450323789S2CID 2156324

[4] Sharir, Micha (1981), "A strong-connectivity algorithm and its applications in data flow analysis", Computers & Mathematics with Applications , 7 : 67–72 , doi : 10.1016/0898-1221(81)90008-0

[5] Tarjan, RE (1972), "深さ優先探索と線形グラフアルゴリズム", SIAM Journal on Computing , 1 (2): 146–160 , doi : 10.1137/0201010 , S2CID 16467262

[6] エドガー・ダイクストラ(1976)『プログラミングの規律』ニュージャージー州：プレンティス・ホール、第25章。

[Fleischer-7] Fleischer, Lisa K.; Hendrickson, Bruce; Pınar, Ali (2000), "On Identifying Strongly Connected Components in Parallel" (PDF) , Parallel and Distributed Processing , Lecture Notes in Computer Science, vol. 1800, pp. 505–511 , doi : 10.1007/3-540-45591-4_68 , ISBN 978-3-540-67442-9

[Parallel-8] Blelloch, Guy E.; Gu, Yan; Shun, Julian; Sun, Yihan (2016), "Parallelism in Randomized Incremental Algorithms" (PDF) , Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '16 , pp. 467– 478, arXiv : 1810.05303 , doi : 10.1145/2935764.2935766 , hdl : 1721.1/146176 , ISBN 9781450342100。

[9] Maurer, PM (2018年2月)、強く連結したランダムグラフの生成(PDF)、国際モデリング・シミュレーション・可視化手法会議 MSV'17、CSREA Press、ISBN 978-1-60132-465-8（ 2019年12月27日取得）

[10] Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "特定の量化ブール式の真偽をテストするための線形時間アルゴリズム", Information Processing Letters , 8 (3): 121–123 , doi : 10.1016/0020-0190(79)90002-4。

[11] Dulmage, AL & Mendelsohn, NS (1958), "二部グラフの被覆", Can. J. Math. , 10 : 517– 534, doi : 10.4153/cjm-1958-052-0 , S2CID 123363425 。

[12] Robbins, HE (1939)、「グラフに関する定理、交通管制の問題への応用」、American Mathematical Monthly、46 (5): 281–283、doi : 10.2307/2303897、JSTOR 2303897 。

[

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[

[