Editing Strongly connected component (section)

==Definitions==
A [[directed graph]] is called '''strongly connected''' if there is a [[path (graph theory)|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.

The [[binary relation]] of being strongly connected is an [[equivalence relation]], and the [[induced subgraph]]s of its [[equivalence class]]es are called '''strongly connected components'''.
Equivalently, a '''strongly connected component''' of a directed graph ''G'' is a subgraph that is strongly connected, and is [[maximal element|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''. A strongly connected component ''C'' is called ''trivial'' when ''C'' consists of a single vertex which is not connected to itself with an edge, and ''non-trivial'' otherwise.<ref>{{citation
 | last1 = Nuutila | first1 = Esko
 | last2 = Soisalon-Soininen | first2 = Eljas
 | doi = 10.1016/0020-0190(94)90047-7
 | issue = 1
 | journal = Information Processing Letters
 | pages = 9–14
 | title = On finding the strongly connected components in a directed graph
 | volume = 49
 | year = 1994}}</ref>

[[File:Graph Condensation.svg|thumb|upright=1.5|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 [[vertex contraction|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 non-trivial strongly connected component contains at least one directed cycle.