巨连通分支

来自集智百科 - 伊辛模型
跳到导航 跳到搜索

此词条暂由彩云小译翻译,未经人工整理和审校,带来阅读不便,请见谅。

本词条由信白初步翻译

文件:Scc.png
Graph with strongly connected components marked

Graph with strongly connected components marked

图:强连通图 Strongly Connected Graph

模板:Graph connectivity sidebar

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V+E)).

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V+E)).

在有向图的数学理论中,如果一个图的每个顶点都可以从其他每个顶点到达,那么这个图就被称为强连接图。一个任意的有向图的强连接成分形成一个分区,构成子图,子图本身也是强连接的。可以在线性时间内(即Θ(V+E))测试一个图的强连接性,或者找到它的巨连通分支。



Definitions

定义

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first.

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first.

如果图的每对顶点之间在每个方向上都有一条路径,则称为强连通图。也就是说,从一对顶点中的第一个顶点到第二个顶点存在一条路径,从第二个顶点到第一个顶点存在另一条路径。

In a directed graph G that may not itself be strongly connected, a pair of vertices u and v are said to be strongly connected to each other if there is a path in each direction between them.

In a directed graph G that may not itself be strongly connected, a pair of vertices u and v are said to be strongly connected to each other if there is a path in each direction between them.

在一个本身可能不是强连接的有向图G中,如果一对顶点 uv 之间在每个方向上都有一条路径,则称它们之间是强连接的。


The binary relation of being strongly connected is an equivalence relation, and the induced subgraphs of its equivalence classes are called strongly connected components.

The binary relation of being strongly connected is an equivalence relation, and the induced subgraphs of its equivalence classes are called strongly connected components.

强连接的二元关系是一种等价关系,其等价类的诱导子图称为巨连通分支 Strongly Connected Components

Equivalently, a strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from G can be included in the subgraph without breaking its property of being strongly connected. The collection of strongly connected components forms a partition of the set of vertices of G.

Equivalently, a strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from G can be included in the subgraph without breaking its property of being strongly connected. The collection of strongly connected components forms a partition of the set of vertices of G.

同理,一个有向图 G 的巨连通分支是一个强连接的子图,并且是最大的,具有这个属性:在不破坏其强连接的属性的情况下,不能从 G 中加入额外的边或顶点。强连通分支的集合构成了G的顶点集的分区。


文件:Graph Condensation.svg
The yellow directed acyclic graph is the condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.

The yellow directed acyclic graph is the condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.

黄色(有向无环图)是蓝色有向图的浓缩。它是通过将蓝色图的每个强连通分支收缩成一个黄色顶点而形成的。

If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of G. A directed graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every nontrivial strongly connected component contains at least one directed cycle.

If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of G. A directed graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every nontrivial strongly connected component contains at least one directed cycle.

如果每个巨连通分支都收缩到一个顶点,那么得到的图就是一个有向无环图,也就是 G 的缩合图,如果且仅如果一个有向图没有超过一个顶点的强连通子图,那么这个图就是无环图,因为一个有向循环是强连接的,每一个非平凡的巨连通分支至少包含一个有向循环。

Algorithms

算法

DFS-based linear-time algorithms

基于DFS的线性时间算法

Several algorithms based on depth first search compute strongly connected components in linear time.

Several algorithms based on depth first search compute strongly connected components in linear time.

几种基于深度优先搜索 Depth First Search 的算法在线性时间内计算巨连接分支。


  • Kosaraju's algorithm uses two passes of depth first search. The first, in the original graph, is used to choose the order in which the outer loop of the second depth first search tests vertices for having been visited already and recursively explores them if not. The second depth first search is on the transpose graph of the original graph, and each recursive exploration finds a single new strongly connected component.[1][2] It is named after S. Rao Kosaraju, who described it (but did not publish his results) in 1978; Micha Sharir later published it in 1981.[3]

Kosaraju算法 Kosaraju's algorithm 使用了两次深度优先搜索。第一次,在原始图中,用于选择第二次深度优先搜索的外循环测试顶点是否已经被访问过的顺序,如果没有,则递归探索它们。第二次深度优先搜索是在原图的转置图上进行的,每次递归探索都会发现一个新的巨连接分支.[4][2] It is named after S. Rao Kosaraju, who described it (but did not publish his results) in 1978; Micha Sharir later published it in 1981.[5]


通过www.DeepL.com/Translator(免费版)翻译

  • Tarjan's strongly connected components algorithm, published by Robert Tarjan in 1972,[6] performs a single pass of depth first search. It maintains a stack of vertices that have been explored by the search but not yet assigned to a component, and calculates "low numbers" of each vertex (an index number of the highest ancestor reachable in one step from a descendant of the vertex) which it uses to determine when a set of vertices should be popped off the stack into a new component.

Tarjan巨连通算法 Tarjan's strongly connected components algorithm ,由Robert Tarjan于1972年提出,[7]执行单次深度优先搜索。它维护一个堆栈(抽象数据类型)Stack 的顶点,这些顶点已经被搜索探索过,但还没有被分配到一个组件中,并计算每个顶点的 "低数"(从顶点的后裔一步步到达的最高祖先的索引号),它用来决定何时应该将一组顶点从堆栈中弹出到一个新的组件中。

  • The path-based strong component algorithm uses a depth first search, like Tarjan's algorithm, but with two stacks. One of the stacks is used to keep track of the vertices not yet assigned to components, while the other keeps track of the current path in the depth first search tree. The first linear time version of this algorithm was published by Edsger W. Dijkstra in 1976.[8]

基于路径的强分量算法]]使用深度优先搜索,就像Tarjan的算法一样,但有两个堆栈。其中一个堆栈用于跟踪尚未分配给组件的顶点,而另一个堆栈则跟踪深度第一搜索树中的当前路径。该算法的第一个线性时间版本由Edsger W. Dijkstra于1976年发表[9]

Although Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm require only one depth-first search rather than two.

The expected sequential running time of this algorithm is shown to be O(n log n), a factor of O(log n) more than the classic algorithms. The parallelism comes from: (1) the reachability queries can be parallelized more easily (e.g. by a BFS, and it can be fast if the diameter of the graph is small); and (2) the independence between the subtasks in the divide-and-conquer process.

虽然Kosaraju的算法在概念上很简单,但Tarjan的算法和基于路径的算法只需要一次深度优先搜索,而不是两次。

该算法的预期顺序运行时间显示为O(n log n),比经典算法多了O(log n)倍。 并行性来自于:(1)可达性查询可以更容易地并行化(例如通过BFS,如果图的直径很小,它可以很快地并行化);(2)分而治之过程中子任务之间的独立性。


This algorithm performs well on real-world graphs, but does not have theoretical guarantee on the parallelism (consider if a graph has no edges, the algorithm requires O(n) levels of recursions).

这种算法在现实世界的图上表现良好,但在理论上不能保证其并行性(考虑如果一个图没有边,该算法需要O(n)级递归。

Reachability-based Algorithms

基于可达性的算法 Reachability-based Algorithms


Blelloch et al. in 2016 shows that if the reachability queries are applied in a random order, the cost bound of O(n log n) still holds. Furthermore, the queries then can be batched in a prefix-doubling manner (i.e. 1, 2, 4, 8 queries) and run simultaneously in one round. The overall span of this algorithm is log2 n reachability queries, which is probably the optimal parallelism that can be achieved using the reachability-based approach.

Blelloch等人在2016年的研究表明,如果按随机顺序应用可达性查询,O(n log n)的成本约束仍然成立。 此外,查询则可以以前缀加倍的方式进行分批(即1,2,4,8个查询),并在一轮中同时运行。 该算法的总体跨度为log2 n个可达性查询,这可能是使用基于可达性的方法所能达到的最佳并行性。

Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize. Fleischer et al.[10] in 2000 proposed a divide-and-conquer approach based on reachability queries, and such algorithms are usually called reachability-based SCC algorithms. The idea of this approach is to pick a random pivot vertex and apply forward and backward reachability queries from this vertex. The two queries partition the vertex set into 4 subsets: vertices reached by both, either one, or none of the searches. One can show that a strongly connected component has to be contained in one of the subsets. The vertex subset reached by both searches forms a strongly connected components, and the algorithm then recurses on the other 3 subsets.

以前的线性时间算法是基于深度优先搜索,一般认为很难并行化。 Fleischer等人[10] 在2000年提出了一种基于可达性查询的分而治之算法 divid-and-conquer algorithm ,这种算法通常被称为基于可达性的SCC算法。 这种方法的思想是选择一个随机的枢轴顶点,并从这个顶点应用前向和后向可到达性查询。 这两个查询将顶点集划分为4个子集:两种搜索、一种搜索或没有搜索到达的顶点。 可以证明,强连接的分量必须包含在其中一个子集中。 两次搜索到达的顶点子集形成一个强连接的成分,然后算法在其他3个子集上递归。


The expected sequential running time of this algorithm is shown to be O(n log n), a factor of O(log n) more than the classic algorithms. The parallelism comes from: (1) the reachability queries can be parallelized more easily (e.g. by a BFS, and it can be fast if the diameter of the graph is small); and (2) the independence between the subtasks in the divide-and-conquer process.

显示该算法的预期顺序运行时间为O(n log n),比经典算法多了O(log n)倍。 并行性来自于:(1)可达性查询可以更容易地并行化(例如通过广度优先搜索 Breadth-first search|BFS ,如果图的直径很小,它可以很快地并行化);(2)分而治之过程中子任务之间的独立性。

This algorithm performs well on real-world graphs,[2] but does not have theoretical guarantee on the parallelism (consider if a graph has no edges, the algorithm requires O(n) levels of recursions).

该算法在真实世界的图上表现良好,[2] ,但在理论上不能保证并行性(考虑如果一个图没有边,算法需要O(n)级的递归)。

Peter M. Maurer describes an algorithm for generating random strongly connected graphs, based on a modification of Tarjan's algorithm to create a spanning tree and adding a minimum of edges such that the result becomes strongly connected. When used in conjunction with the Gilbert or Erdős-Rényi models with node relabelling, the algorithm is capable of generating any strongly connected graph on n nodes, without restriction on the kinds of structures that can be generated.

Peter M. Maurer描述了一种生成随机强连接图的算法,该算法基于对Tarjan算法的修改,以创建一棵生成树,并增加最小的边,从而使结果成为强连接图。 当与Gilbert或Erdős-Rényi模型结合使用时,该算法能够在节点上生成任何强连接图,而不限制可以生成的结构种类。


Blelloch et al.[11] in 2016 shows that if the reachability queries are applied in a random order, the cost bound of O(n log n) still holds. Furthermore, the queries then can be batched in a prefix-doubling manner (i.e. 1, 2, 4, 8 queries) and run simultaneously in one round. The overall span of this algorithm is log2 n reachability queries, which is probably the optimal parallelism that can be achieved using the reachability-based approach.

Blelloch等人[11]在2016年的研究表明,如果以随机顺序应用可达性查询,O(n log n)的成本约束仍然成立。 此外,查询就可以以前缀加倍的方式进行分批(即1,2,4,8次查询),并在一轮中同时运行。 该算法的总体并行算法分析是log2n可达性查询,这可能是使用基于可达性的方法可以达到的最佳并行性。


Algorithms for finding strongly connected components may be used to solve 2-satisfiability problems (systems of Boolean variables with constraints on the values of pairs of variables): as showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable v such that v and its complement are both contained in the same strongly connected component of the implication graph of the instance.

寻找巨连通分支的算法可以用来解决2-可满足性问题(对变量对值有约束的布尔变量系统):如图所示,如果且仅如果有一个变量v,使v和它的补码都包含在该实例的内涵图的同一个强连接分量中,那么一个2-可满足性实例就是不满足的。

Generating random strongly connected graphs

生成随机强连通图


Strongly connected components are also used to compute the Dulmage–Mendelsohn decomposition, a classification of the edges of a bipartite graph, according to whether or not they can be part of a perfect matching in the graph.

巨连通分支也被用来计算Dulmage-Mendelsohn分解 Dulmage - Mendelsohn decompsoition ,即根据它们是否可以成为图中完美匹配的一部分,对二元图的边进行分类。

Peter M. Maurer describes an algorithm for generating random strongly connected graphs,[12] based on a modification of Tarjan's algorithm to create a spanning tree and adding a minimum of edges such that the result becomes strongly connected. When used in conjunction with the Gilbert or Erdős-Rényi models with node relabelling, the algorithm is capable of generating any strongly connected graph on n nodes, without restriction on the kinds of structures that can be generated.

Peter M. Maurer描述了一种生成随机强连接图的算法,[13]基于对Tarjan算法的修改,创建一棵生成树,并添加最少的边,使结果成为强连接图。 当与Gilbert或Erdős-Rényi模型结合使用时,该算法能够在 n 节点上生成任何强连接图,而不限制可以生成的结构种类。

Applications

应用

A directed graph is strongly connected if and only if it has an ear decomposition, a partition of the edges into a sequence of directed paths and cycles such that the first subgraph in the sequence is a cycle, and each subsequent subgraph is either a cycle sharing one vertex with previous subgraphs, or a path sharing its two endpoints with previous subgraphs.

如果且仅如果一个有向图有一个耳分解 Ear Decomposition ,即把边分割成有向路径和循环的序列,使序列中的第一个子图是一个循环,以后的每一个子图都是一个循环与前面的子图共享一个顶点,或者是一个路径与前面的子图共享它的两个端点,那么这个图就是强连接的。

Algorithms for finding strongly connected components may be used to solve 2-satisfiability problems (systems of Boolean variables with constraints on the values of pairs of variables): as 脚本错误:没有“Footnotes”这个模块。 showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable v such that v and its complement are both contained in the same strongly connected component of the implication graph of the instance.[14]

寻找强连接分量的算法可以用来解决2-可满足性问题(对变量对的值有约束的布尔变量系统):如脚本错误:没有“Footnotes”这个模块。所示,一个2-可满足性实例是不可满足的,如果且仅当有一个变量 v 使得 v 和它的补码都包含在该实例的内涵图的同一个强连接分量中。[15]

Strongly connected components are also used to compute the Dulmage–Mendelsohn decomposition, a classification of the edges of a bipartite graph, according to whether or not they can be part of a perfect matching in the graph.[16]

Related results

相关研究

A directed graph is strongly connected if and only if it has an ear decomposition, a partition of the edges into a sequence of directed paths and cycles such that the first subgraph in the sequence is a cycle, and each subsequent subgraph is either a cycle sharing one vertex with previous subgraphs, or a path sharing its two endpoints with previous subgraphs.

如果且仅如果一个有向图具有耳分解,即把边分割成有向路径和循环的序列,使序列中的第一个子图是一个循环,随后的每一个子图都是与前一个子图共享一个顶点的循环,或者是与前一个子图共享其两个端点的路径,则该图是强连接的。


According to Robbins' theorem, an undirected graph may be oriented in such a way that it becomes strongly connected, if and only if it is 2-edge-connected. One way to prove this result is to find an ear decomposition of the underlying undirected graph and then orient each ear consistently.<ref>{{citation

| last = Robbins | first = H. E. | author-link = Herbert Robbins

Category:Graph connectivity

类别: 图形连接性

| journal = American Mathematical Monthly

Category:Directed graphs

类别: 有向图


This page was moved from wikipedia:en:Strongly connected component. Its edit history can be viewed at 巨连通分支/edithistory

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 22.5, pp. 552–557.
  2. 2.0 2.1 2.2 2.3 Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013), "On fast parallel detection of strongly connected components (SCC) in small-world graphs" (PDF), Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis - SC '13, pp. 1–11, doi:10.1145/2503210.2503246, ISBN 9781450323789
  3. 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
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 22.5, pp. 552–557.
  5. {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
  6. Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160, doi:10.1137/0201010
  7. Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160, doi:10.1137/0201010
  8. [[Edsger Dijkstra Although Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm require only one depth-first search rather than two.|Dijkstra, Edsger]] (1976), A Discipline of Programming Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize. Fleischer et al. in 2000 proposed a divide-and-conquer approach based on reachability queries, and such algorithms are usually called reachability-based SCC algorithms. The idea of this approach is to pick a random pivot vertex and apply forward and backward reachability queries from this vertex. The two queries partition the vertex set into 4 subsets: vertices reached by both, either one, or none of the searches. One can show that a strongly connected component has to be contained in one of the subsets. The vertex subset reached by both searches forms a strongly connected components, and the algorithm then recurses on the other 3 subsets., Prentice Hall, Ch. 25 line feed character in |title= at position 28 (help); line feed character in |author-link= at position 16 (help).
  9. [[Edsger Dijkstra Although Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm require only one depth-first search rather than two.|Dijkstra, Edsger]] (1976), A Discipline of Programming Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize. Fleischer et al. in 2000 proposed a divide-and-conquer approach based on reachability queries, and such algorithms are usually called reachability-based SCC algorithms. The idea of this approach is to pick a random pivot vertex and apply forward and backward reachability queries from this vertex. The two queries partition the vertex set into 4 subsets: vertices reached by both, either one, or none of the searches. One can show that a strongly connected component has to be contained in one of the subsets. The vertex subset reached by both searches forms a strongly connected components, and the algorithm then recurses on the other 3 subsets., Prentice Hall, Ch. 25 line feed character in |title= at position 28 (help); line feed character in |author-link= at position 16 (help).
  10. 10.0 10.1 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, 1800, pp. 505–511, doi:10.1007/3-540-45591-4_68, ISBN 978-3-540-67442-9
  11. 11.0 11.1 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, doi:10.1145/2935764.2935766, ISBN 9781450342100.
  12. Maurer, P. M., Generating strongly connected random graphs (PDF), Int'l Conf. Modeling, Sim. and Vis. Methods MSV'17, CSREA Press, ISBN 1-60132-465-0, retrieved December 27, 2019
  13. Maurer, P. M., Generating strongly connected random graphs (PDF), Int'l Conf. Modeling, Sim. and Vis. Methods MSV'17, CSREA Press, ISBN 1-60132-465-0, retrieved December 27, 2019
  14. Aspvall, Bengt According to Robbins' theorem, an undirected graph may be oriented in such a way that it becomes strongly connected, if and only if it is 2-edge-connected. One way to prove this result is to find an ear decomposition of the underlying undirected graph and then orient each ear consistently.; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4 line feed character in |first1= at position 6 (help).
  15. Aspvall, Bengt According to Robbins' theorem, an undirected graph may be oriented in such a way that it becomes strongly connected, if and only if it is 2-edge-connected. One way to prove this result is to find an ear decomposition of the underlying undirected graph and then orient each ear consistently.; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4 line feed character in |first1= at position 6 (help).
  16. Dulmage, A. L. & Mendelsohn, N. S. (1958), "Coverings of bipartite graphs", Can. J. Math., 10: 517–534, doi:10.4153/cjm-1958-052-0.