(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 G1=(V1, E1)..., Gm=(Vm, Em) be its connected components. Every vertex is in exactly in one connected component. Formally, for all i ≠ j, Vi∩ Vj=ø. Further, V=V1∪...∪ Vm and E=E1∪...∪ Em.
Author: AL
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:23:28 2004.
HTML page formatted Mon Dec 19 14:07:47 2005.
Cite this as:
Alen Lovrencic, "connected components", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/connectedComponents.html
