connected components

(definition)

Definition: The set of maximally connected components of an undirected graph.

Generalization (I am a kind of ...)
partition.

See also connected graph, biconnected component, undirected graph, subgraph, clique, strongly connected components.

Note: If a graph is connected, it has only one connected component. Often the term "component" is used, with the "connected" property understood.

Let G=(V, E) be a graph and G₁=(V₁, E₁)..., G_m=(V_m, E_m) be its connected components. Every vertex is in exactly in one connected component, that is, the components partition(1) V. Formally, for all i ≠ j, V_i∩ V_j=ø. Further, V=V₁∪...∪ V_m and E=E₁∪...∪ E_m.

Author: AL

Implementation

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 18 October 2007.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Alen Lovrencic, "connected components", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 18 October 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/connectedComponents.html