Strongly connected component
A directed graph is called strongly connected if there is a path from each vertex in the graph to
every other vertex. In particular, this means paths in each direction; a path from a to b and also
a path from b to a.
The strongly connected components of a directed graph G are its maximal strongly connected subgraphs.
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 (nontrivial) strongly connected subgraphs
(because a cycle is strongly connected, and every strongly connected graph contains at least one cycle).
Kosaraju's algorithm, Tarjan's algorithm and Gabow's algorithm all efficiently compute the strongly connected
components of a directed graph, but Tarjan's and Gabow's are favoured in practice since they require only one
depth-first search rather than two.
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 Aspvall, Plass & Tarjan (1979)
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.
沒有留言:
張貼留言