Editing Component (graph theory) (section)

{{good article}}
{{Short description|Maximal subgraph whose vertices can reach each other}}
[[Image:Pseudoforest.svg|thumb|240px|A graph with three components]]
In [[graph theory]], a '''component''' of an [[undirected graph]] is a [[connected graph|connected]] [[Glossary of graph theory#subgraph|subgraph]] that is not part of any larger connected subgraph. The components of any graph partition its vertices into [[disjoint set]]s, and are the [[induced subgraph]]s of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called '''connected components'''.

The number of components in a given graph is an important [[graph invariant]], and is closely related to invariants of [[matroid]]s, [[topological space]]s, and [[matrix (mathematics)|matrices]]. In [[random graph]]s, a frequently occurring phenomenon is the incidence of a [[giant component]], one component that is significantly larger than the others; and of a [[percolation threshold]], an edge probability above which a giant component exists and below which it does not.

The components of a graph can be constructed in [[linear time]], and a special case of the problem, [[connected-component labeling]], is a basic technique in [[image analysis]]. [[Dynamic connectivity]] algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In [[computational complexity theory]], connected components have been used to study algorithms with limited [[space complexity]], and [[sublinear time]] algorithms can accurately estimate the number of components.