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 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.
Kosaraju's algorithm, Tarjan's algorithm and the path-based strong component algorithm all efficiently compute the strongly connected components of a directed graph, but Tarjan's and the path-based algorithm 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.
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.
Famous quotes containing the words strongly, connected and/or component:
“However strongly they resist it, our kids have to learn that as adults we need the companionship and love of other adults. The more direct we are about our needs, the easier it may be for our children to accept those needs. Their jealousy may come from a fear that if we adults love each other we might not have any left for them. We have to let them know that it’s a different kind of love.”
—Ruth Davidson Bell. Ourselves and Our Children, by Boston Women’s Health Book Collective, ch. 3 (1978)
“Before I had my first child, I never really looked forward in anticipation to the future. As I watched my son grow and learn, I began to imagine the world this generation of children would live in. I thought of the children they would have, and of their children. I felt connected to life both before my time and beyond it. Children are our link to future generations that we will never see.”
—Louise Hart (20th century)
“... no one knows anything about a strike until he has seen it break down into its component parts of human beings.”
—Mary Heaton Vorse (1874–1966)