強く連結された成分

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

定義

有向グラフは、グラフの各頂点のペアの間に各方向にパスがある場合、強く接続されていると言われます。つまり、ペアの最初の頂点から 2 番目の頂点へのパスが存在し、2 番目の頂点から最初の頂点への別のパスが存在します。有向グラフG自体は強く接続されていない可能性がありますが、頂点uとvのペアの間に各方向にパスがある場合、それらのペアは互いに強く接続されていると言われます。

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

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

アルゴリズム

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

深さ優先探索に基づくいくつかのアルゴリズムは、強く連結されたコンポーネントを線形時間で計算します。

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

Kosaraju のアルゴリズムは概念的には単純ですが、Tarjan のアルゴリズムとパスベースのアルゴリズムでは、深さ優先検索が 2 回ではなく 1 回だけ必要です。

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

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

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

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

ランダムな強連結グラフの生成

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

アプリケーション

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

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

参照

参考文献

^ 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 and McGraw-Hill、2001年。ISBN 0-262-03293-7。セクション22.5、pp.552–557。
^ ab Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013)、「スモールワールドグラフにおける強連結成分 (SCC) の高速並列検出について」(PDF)、高性能コンピューティング、ネットワーキング、ストレージ、分析に関する国際会議 - SC '13 の議事録、pp. 1–11、doi :10.1145/2503210.2503246、ISBN 9781450323789、S2CID 2156324
^ シャリル、ミカ（1981）、「強連結アルゴリズムとデータフロー解析への応用」、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)、「並列で強く接続されたコンポーネントを識別する方法」(PDF)、並列および分散処理、コンピュータサイエンスの講義ノート、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)、「ランダム化増分アルゴリズムの並列処理」(PDF)、第28回ACMアルゴリズムとアーキテクチャの並列処理に関するシンポジウムの議事録 - SPAA '16、pp. 467–478、doi : 10.1145/2935764.2935766、hdl : 1721.1/146176、ISBN 9781450342100。
^ Maurer, PM (2018年2月)、強く連結されたランダムグラフの生成(PDF)、Int'l Conf. Modeling, Sim. and Vis. Methods 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。
^ ロビンズ、HE (1939)、「グラフに関する定理と交通管制の問題への応用」、アメリカ数学月刊誌、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 and McGraw-Hill、2001年。ISBN 0-262-03293-7。セクション22.5、pp.552–557。

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

[4] シャリル、ミカ（1981）、「強連結アルゴリズムとデータフロー解析への応用」、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)、「並列で強く接続されたコンポーネントを識別する方法」(PDF)、並列および分散処理、コンピュータサイエンスの講義ノート、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)、「ランダム化増分アルゴリズムの並列処理」(PDF)、第28回ACMアルゴリズムとアーキテクチャの並列処理に関するシンポジウムの議事録 - SPAA '16、pp. 467–478、doi : 10.1145/2935764.2935766、hdl : 1721.1/146176、ISBN 9781450342100。

[9] Maurer, PM (2018年2月)、強く連結されたランダムグラフの生成(PDF)、Int'l Conf. Modeling, Sim. and Vis. Methods 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] ロビンズ、HE (1939)、「グラフに関する定理と交通管制の問題への応用」、アメリカ数学月刊誌、46 (5): 281–283、doi :10.2307/2303897、JSTOR 2303897。

定義