In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components. A graph that is itself connected has exactly one connected component, consisting of the whole graph.

An equivalence relation

An alternative way to define connected components involves the equivalence classes of an equivalence relation

Equivalence relation

In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

 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

Equivalence relation

In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

, since:

• It is reflexive
  Reflexive relation
  In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
  
  : There is a trivial path of length zero from any vertex to itself.
• It is symmetric
  Symmetric relation
  In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
  
  : If there is a path from u to v, the same edges form a path from v to u.
• It is transitive
  Transitive relation
  In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
  
  : 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 connected components are then the induced subgraphs formed by the equivalence classes of this relation.

The number of connected components

The number of connected components is an important topological invariant of a graph. In topological graph theory

Topological graph theory

In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....

 it can be interpreted as the zeroth Betti number

Betti number

In algebraic topology, a mathematical discipline, the Betti numbers can be used to distinguish topological spaces. Intuitively, the first Betti number of a space counts the maximum number of cuts that can be made without dividing the space into two pieces....

 of the graph. In algebraic graph theory

Algebraic graph theory

Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...

 it equals the multiplicity of 0 as an eigenvalue of the Laplacian matrix

Laplacian matrix

In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...

 of the graph. It is also the index of the first nonzero coefficient of the chromatic polynomial

Chromatic polynomial

The chromatic polynomial is a polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte...

 of a graph. Numbers of connected components play a key role in the Tutte theorem

Tutte theorem

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings...

 characterizing graphs that have perfect matchings, and in the definition of graph toughness

Graph toughness

In graph theory, toughness is a measure of the connectivity of a graph. A graph is said to be -tough for a given real number if, for every integer , cannot be split into different connected components by the removal of fewer than vertices...

.

Algorithms

It is straightforward to compute the connected components of a graph in linear time using either breadth-first search

Breadth-first search

In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...

 or depth-first search

Depth-first search

Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....

. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected 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 connected component. Hopcroft and Tarjan (1973) describe essentially this algorithm, and state that at that point it was "well known".

There are also efficient algorithms to dynamically track the connected components of a graph as vertices and edges are added, as a straightforward application of disjoint-set data structure

Disjoint-set data structure

In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...

s. These algorithms require amortized

Amortized analysis

In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...

 O(α(n)) time per operation, where adding vertices and edges and determining the connected component in which a vertex falls are both operations, and α(n) is a very slow-growing inverse of the very quickly-growing Ackermann function

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...

. A related problem is tracking connected components as all edges are deleted from a graph, one by one; an algorithm exists to solve this with constant time per query, and O(|V||E|) time to maintain the data structure; this is an amortized cost of O(|V|) per edge deletion. For forests, the cost can be reduced to O(q + |V| log |V|), or O(log |V|) amortized cost per edge deletion.

Researchers have also studied algorithms for finding connected components in more limited models of computation, such as programs in which the working memory is limited to a logarithm

Logarithm

The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...

ic number of bits (defined by the complexity class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

 L

L (complexity)

In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...

). asked whether it is possible to test in logspace whether two vertices belong to the same connected component of an undirected graph, and defined a complexity class SL

SL (complexity)

In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...

 of problems logspace-equivalent to connectivity. Finally succeeded in finding an algorithm for solving this connectivity problem in logarithmic space, showing that L = SL.

See also

• Strongly connected component
  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....
  
  , a related concept for directed graph
  Directed graph
  A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
  
  s
• Biconnected component
  Biconnected component
  In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or articulation points...
  
  
• Modular decomposition
  Modular decomposition
  In graph theory, the modular decomposition is a decomposition of an undirected graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another...
  
  , for a proper generalization of connected components on undirected graphs
• Connected-component labeling, a basic technique in computer image analysis based on connected components of graphs
• Percolation theory
  Percolation theory
  In mathematics, percolation theory describes the behavior of connected clusters in a random graph. The applications of percolation theory to materials science and other domains are discussed in the article percolation.-Introduction:...
  
  , a theory describing the behavior of connected components in random subgraphs of grid graphs
• Centrality
  Centrality
  Within graph theory and network analysis, there are various measures of the centrality of a vertex within a graph that determine the relative importance of a vertex within the graph...
  
  

External links

• Connected components, Steven Skiena, The Stony Brook Algorithm Repository