強連通分量

在有向圖的數學理論中，如果一個圖的每一個頂點都可從該圖其他任意一點到達，則稱該圖是強連通的。在任意有向圖中能夠實現強連通的部分我們稱其為強連通分量。判斷一個圖是否為強連通以及找到一個圖強連通分量只需要線性時間（Θ(V + E)）。

定義

如果有向圖的每一對頂點之間在每個方向上都有一條路徑，則稱該有向圖為強連通圖。也就是說，頂點對中的第一個頂點到第二個頂點存在一條路徑，從第二個頂點到第一個頂點存在另一條路徑。在本身可能不是強連通的有向圖 $G$ 中，如果一對頂點 $u$ 和 $v$ 之間在每個方向上都有一條路徑，則稱它們是強連通的。

強連通的二元關係是一個等價關係，其等價類的導出子圖稱為強連通分量。同樣地，有向圖 $G$ 的強連通分量是一個強連通的子圖，並且在這個子圖上是最大的，這意味着在不破壞 $G$ 的強連通特性的情況下，任何來自 $G$ 的額外邊或頂點都不能包含在子圖中。強連通分量的集合構成了 $G$ 的頂點集的一個子集。

黃色有向無環圖是通過將藍色有向圖的每個強連通分量壓縮成一個單一的黃色頂點而形成的

如果將每個強連通分量收縮為單個頂點，則得到的圖是一個有向無環圖。當且僅當有向圖不包含具有多個頂點的強連通子圖時，它就是無環的，這是因為如果有向圖是強連通的，則每個非單調強連通分量至少包含一個有向環。

算法

基於DFS的線性時間算法

幾種基於深度優先搜索並能在線性時間內計算強連通分量的算法。

Kosaraju算法使用了兩次深度優先搜索。在原始圖中，第一次搜索用於決定第二個深度優先搜索的外層循環的順序，該循環測試已經訪問過的頂點，如果沒有，則用遞歸的手段搜索它們。第二次深度優先搜索是在原始圖的轉置圖上進行，每個遞歸搜索都能找到一個新的強連通分量。^[1]這種算法以其首次提出者S·拉奧·科薩拉朱（英語：S. Rao Kosaraju）的名字命名，但是並沒有被發表，直到1981年才被米查·沙里爾發表。^[2]
Tarjan演算法:由羅伯特·塔揚於1972年發表^[3]，是一種深度優先搜索方式。

應用

尋找強連通分量的算法可以用來解決2-SAT（英語：2-satisfiability）問題（由帶有對於變量對的值的限制的布爾變量構成的系統）：如Aspvall, Plass & Tarjan (1979)所示，一個2-SAT（英語：2-satisfiability）實例是無解的，當且僅當有一個變量v使得v和它的互補被包含在實例的隱含圖的同一個強連通分量中。^[4]

強連通分量也被用來計算Dulmage–Mendelsohn 分解（英語：Dulmage–Mendelsohn decomposition），一種二分圖的邊的分類，根據它們能否作為圖中的完美匹配。^[5]

參考文獻

^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.
^ Sharir, Micha, A strong-connectivity algorithm and its applications in data flow analysis, Computers & Mathematics with Applications, 1981, 7: 67–72, doi:10.1016/0898-1221(81)90008-0 
^ Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1972, 1 (2): 146–160, doi:10.1137/0201010
^ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E., A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters, 1979, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4 .
^ Dulmage, A. L. & Mendelsohn, N. S., Coverings of bipartite graphs, Can. J. Math., 1958, 10: 517–534, S2CID 123363425, doi:10.4153/cjm-1958-052-0 .

外部連結

Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E., A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters, 1979, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4 .
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.

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

[3] Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1972, 1 (2): 146–160, doi:10.1137/0201010

[4] Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E., A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters, 1979, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4 .

[5] Dulmage, A. L. & Mendelsohn, N. S., Coverings of bipartite graphs, Can. J. Math., 1958, 10: 517–534, S2CID 123363425, doi:10.4153/cjm-1958-052-0 .

[1]

[2]

[3]

[4]

[5]