强连通分量
维基百科，自由的百科全书
 |
本条目沒有或只有很少鏈入頁面。（2012年4月10日） |
 |
本条目需要补充更多来源。（2012年4月10日） |
強連通元件是图论中的概念。图论中，强连通图指每一個頂點皆可以經由該圖上的邊抵達其他的每一個點的有向圖。意即對於此圖上每一個點對(Va,Vb)，皆存在路徑Va→Vb以及Vb→Va。強連通元件則是指一張有向圖 G 的极大强连通子圖 G'。如果將每一個強連通元件縮成一個點，則原圖 G 將會變成一張有向無環圖。一張圖被稱為有向無環圖若且唯若此圖不具有點集合數量大於一的強連通分量，因為有向環即是一個強連通元件，而且任何的強連通元件皆具有至少一個有向環。
Kosaraju算法、Tarjan算法、Gabow算法皆為尋找有向圖強連通元件的有效算法。但是由於在Tarjan 算法和 Gabow 算法的過程中，只需要進行一次的深度優先搜索，因而相對 Kosaraju 算法較有效率。
尋找強連通分量的演算法，也可以用來解 2-SAT(2-satisfiability) 問題。Aspvall， Plass & Tarjan (1979)
根據 Robbins理论，當一個無向圖為雙連接圖時，也會形成強連通。
參見 [编辑]
參考 [编辑]
- 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.
