Strongly Connected Graph Component

A Strongly Connected Graph Component is a connected directed graph that is a graph component.

• AKA: SCGC.
• Context:
  • It can (typically) be a component of a Directed Graph.
• Example(s):
  • the SCGC of a Web Snapshot[1].
  • …
• Counter-Example(s):
  • a Weakly Connected Graph Component.
• See: Graph Component, Maximal Clique, Reachability, Partition of a Set, Linear Time, Web Graph Topology.

---

---

References

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Strongly_connected_component Retrieved:2014-10-14.
  • 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.

2014

• http://webdatacommons.org/hyperlinkgraph/2014-04/topology.html
  • This document provides basic statistics about the topology of the Web Data Commons - Hyperlink Graph extracted from the Common Crawl Corpus released in April 2014, covering 1.7 billion web pages and 64 billion hyperlinks between these pages. ... The graph of 2014 is well connected (91% of all nodes) the largest strongly connected component consists of only 19% of all nodes, which is most like due to the selected crawling strategy.

2013

• http://en.wikipedia.org/wiki/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 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 Template:Harvtxt 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.

---