Connected component (graph theory)
From Wikipedia, the free encyclopedia
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and to which no more vertices or edges can be added while preserving its connectivity. That is, it is a maximal connected subgraph. For example, the graph shown in the illustration at right has three connected components. A graph that is itself connected has exactly one connected component, consisting of the whole graph.
Contents |
[edit] An equivalence relation
An alternative way to define connected 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 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 connected components are then the induced subgraphs formed by the equivalence classes of this relation.
[edit] The number of connected components
The number of connected components is an important topological invariant of a graph. In topological graph theory it can be interpreted as the zeroth Betti number of the graph. 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 connected components play a key role in the Tutte theorem characterizing graphs that have perfect matchings, and in the definition of graph toughness.
[edit] Algorithms
It is straightforward to compute the connected components of a graph in linear time 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 connected component containing v 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.
Algorithms 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 logarithmic number of bits (defined by the complexity class L). Lewis & Papadimitriou (1982) 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 of problems logspace-equivalent to connectivity. Finally Reingold (2008) succeeded in finding an algorithm for solving this connectivity problem in logarithmic space, showing that L = SL.
[edit] See also
- Strongly connected component, a related concept for directed graphs
- Connected component labeling, a basic technique in computer image analysis based on connected components of graphs
- Percolation theory, a theory describing the behavior of connected components in random subgraphs of grid graphs
[edit] References
- Lewis, Harry R.; Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Theoretical Computer Science 19 (2): 161–187, doi:.
- Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM 55 (4): Article 17, 24 pages, doi:.
[edit] External links
- Connected components, Steven Skiena, The Stony Brook Algorithm Repository
