强连通分量
在有向图的数学理论中,如果一个图的每一个顶点都可从该图其他任意一点到达,则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为强连通分量。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间(Θ(V + E))。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Scc-1.svg/220px-Scc-1.svg.png)
定义
编辑如果有向图的每一对顶点之间在每个方向上都有一条路径,则称该有向图为强连通图。也就是说,顶点对中的第一个顶点到第二个顶点存在一条路径,从第二个顶点到第一个顶点存在另一条路径。在本身可能不是强连通的有向图 中,如果一对顶点 和 之间在每个方向上都有一条路径,则称它们是强连通的。
强连通的二元关系是一个等价关系,其等价类的导出子图称为强连通分量。同样地,有向图 的强连通分量是一个强连通的子图,并且在这个子图上是最大的,这意味着在不破坏 的强连通特性的情况下,任何来自 的额外边或顶点都不能包含在子图中。强连通分量的集合构成了 的顶点集的一个子集。
如果将每个强连通分量收缩为单个顶点,则得到的图是一个有向无环图。当且仅当有向图不包含具有多个顶点的强连通子图时,它就是无环的,这是因为如果有向图是强连通的,则每个非单调强连通分量至少包含一个有向环。
算法
编辑基于DFS的线性时间算法
编辑几种基于深度优先搜索并能在线性时间内计算强连通分量的算法。
应用
编辑寻找强连通分量的算法可以用来解决2-SAT问题(由带有对于变量对的值的限制的布尔变量构成的系统):如Aspvall, Plass & Tarjan (1979) 所示,一个2-SAT实例是无解的,当且仅当有一个变量v使得v和它的互补被包含在实例的隐含图的同一个强连通分量中。[4]
强连通分量也被用来计算Dulmage–Mendelsohn 分解,一种二分图的边的分类,根据它们能否作为图中的完美匹配。[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.