Component (graph theory)

A graph with three components.

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are also sometimes called connected components.

Definitions and examples

A component of a given undirected graph may be defined as a connected subgraph that is not part of any larger connected subgraph. Every vertex $v$ of a graph belongs to one of the graph's components, which may be found as the induced subgraph of the set of vertices reachable from $v$. For instance, the graph shown in the illustration has three components. As additional examples of this general rule, we have the following special cases:

• In an empty graph, each vertex forms a component with one vertex and zero edges. More generally a component of this type is formed for every isolated vertex in any graph.
• In a connected graph, there is exactly one component, the whole graph.

Another way to define components involves the equivalence classes of an equivalence relation that is defined on the vertices of the graph. In an undirected graph, a vertex $v$ is reachable from a vertex $u$ if there is a path from $u$ to $v$. In this definition, a single vertex is counted as a path of length zero, and the same vertex may occur more than once within a path. Reachability is an equivalence relation, since:

• It is reflexive: There is a trivial path of length zero from any vertex to itself.
• It is symmetric: If there is a path from $u$ to $v$, the same edges in the reverse order form a path from $v$ to $u$.
• It is transitive: If there is a path from $u$ to $v$ and a path from $v$ to $w$, the two paths may be concatenated together to form a path from $u$ to $w$.

The equivalence classes of this relation partition the vertices of the graph into disjoint sets, subsets of vertices that are all reachable from each other, with no additional reachable pairs outside of any of these subsets. Each vertex belongs to exactly one equivalence class. The components are then the induced subgraphs formed by each of these equivalence classes.

Number of components

A graph can be interpreted as a topological space in multiple ways, for instance by placing its vertices as points in general position in three-dimensional Euclidean space and representing its edges as line segments between those points. The components of a graph can be generalized through these interpretations as the number of topological connected components of the corresponding space. Just as the number of connected components is an important topological invariant, the zeroth Betti number of a space, the number of components of a graph is an important graph invariant, and in topological graph theory it can be interpreted as the zeroth Betti number of the graph.

The same number arises in other ways in graph theory as well. In algebraic graph theory it equals the multiplicity of 0 as an eigenvalue of the Laplacian matrix of the graph. It is also the index of the first nonzero coefficient of the chromatic polynomial of a graph. Numbers of components play a key role in the Tutte theorem characterizing graphs that have perfect matchings, and in the definition of graph toughness.

Algorithms

It is straightforward to compute the components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex $v$ will find the entire component containing $v$ (and no more) before returning. To find all the components of a graph, loop through its vertices, starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found component. Hopcroft & Tarjan (1973) describe essentially this algorithm, and state that at that point it was already "well known".

There are also efficient algorithms to dynamically track the components of a graph as vertices and edges are added, by using a disjoint-set data structure to keep track of the partition of the vertices into equivalence classes, replacing any two classes by their union when an edge connecting them is added. These algorithms take amortized time $O(\alpha (n))$ per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and $O(\alpha (n))$ is a very slowly growing inverse of the very quickly growing Ackermann function. One application of this sort of incremental connectivity algorithm is in Kruskal's algorithm for minimum spanning trees, which adds edges to a graph in sorted order by length and includes an edge in the minimum spanning tree only when it connects two different components of the previously-added subgraph.

Components of graphs have been used in computational complexity theory to study the power of Turing machines that have a working memory limited to a logarithmic number of bits, with the much larger input accessible only through read access rather than being modifiable. The problems that can be solved by machines limited in this way define the complexity class L. It was unclear for many years whether connected components could be found in this model, when formalized as a decision problem of testing whether two vertices belong to the same component, and in 1982 a related complexity class, SL, was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space reductions. Finally, in 2008, it was proven that this connectivity problem can be solved in logarithmic space, and therefore that SL = L.

In random graphs

Main article: Giant component

In random graphs the sizes of components are given by a random variable, which, in turn, depends on the specific model. In the $G(n,p)$ version of the Erdős–Rényi model, a graph on $n$ vertices is generated by choosing randomly and independently for each pair of vertices whether to include an edge connecting that pair, with probability $p$ of including an edge and probability $1-p$ of leaving those two vertices without an edge connecting them. The connectivity of this model depends on $p$, and there are three different ranges of $p$ with very different behavior from each other (with high probability):

Subcritical $np<1$

In this range of $p$, all components are simple and very small. The largest component has size $|C_{1}|=O(\log n)$. The graph is a pseudoforest, and most of its components are trees.

Critical $np=1$

There is a single giant component with $|C_{1}|=O(n^{2/3})$; the remaining components are small, with size $O(\log n)$.

Supercritical $np>1$

The size of the giant component becomes linear, and for large values of $p$ approaches the whole graph: $|C_{1}|\approx yn$ where $y=y(np)$ is the positive solution to the equation $e^{-pny}=1-y.$ Again, all remaining components are small.

For a different model, the random subgraphs of grid graphs, the connected components are described by percolation theory.

See also

• Strongly connected component, a related concept for directed graphs
• Biconnected component
• Connected-component labeling, a basic technique in computer image analysis based on components of graphs

External links

• MATLAB code to find components in undirected graphs, MATLAB File Exchange.
• Connected components, Steven Skiena, The Stony Brook Algorithm Repository