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.

### Other articles related to "strongly connected component, component, components, connected, strongly connected components":

... same reachability relation as G, then H consists of A directed cycle for each

**strongly connected component**of G, connecting together the vertices in this

**component**An edge xy ... of G is a directed acyclic graph that has a vertex for every

**strongly connected component**of G and an edge for every two

**components**that are

**connected**by an edge in G ... in the transitive reduction of the condensation, plus the number of vertices in nontrivial

**strongly connected components**(

**components**with more than one vertex) ...

... Occasionally

**connected**computing (OCC) is a term used in computing for an architecture or framework which permits running some aspects of a web application when not ...

... Begusarai is well

**connected**to other parts of Bihar and India through railways as well as roads ... Rajendra Setu on the Ganges is

**connected**to Mokama and Hathidah ... Interior parts of the district are well

**connected**to the main roads ...

### Famous quotes containing the words component, strongly and/or connected:

“... 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)

“The disabusing a man *strongly* possessed with an opinion of his own worth is the very same ill office that was done to the fool at Athens, who fancied all the ships that came into the harbor were his own.”

—François, Duc De La Rochefoucauld (1613–1680)

“War and culture, those are the two poles of Europe, her heaven and hell, her glory and shame, and they cannot be separated from one another. When one comes to an end, the other will end also and one cannot end without the other. The fact that no war has broken out in Europe for fifty years is *connected* in some mysterious way with the fact that for fifty years no new Picasso has appeared either.”

—Milan Kundera (b. 1929)