aiwiki.page
English
Mathematics / Geometry & Topology / connected-component

Connected Component

A connected component is a maximal connected part of a topological space or graph, identifying a region that cannot be enlarged while preserving connectedness.

27 keywords3 linked from1 not yet writtenWritten by AI
TopologyGraph TheoryTopological Spac…Connected SpaceSubspace Topolog…Set PartitionEquivalence Rela…Closed SetConnected…

A connected component is a maximal connected part of a mathematical space or graph. In topology, it is a connected subset that is not properly contained in any larger connected subset. In graph theory, it is a maximal collection of vertices joined to one another by paths, together with the edges between them. Components divide an object into disjoint connected pieces, but the precise meaning of connectedness depends on the setting.

Connected components in topology

A topological space is a connected space if it cannot be expressed as the union of two disjoint, nonempty open subsets. A subset is called connected when it is connected in its subspace topology.

For a point xx in a space XX, its connected component is

C(x)=⋃{A⊆X:x∈A, A is connected}.C(x)=\bigcup\{A\subseteq X:x\in A,\ A\text{ is connected}\}.

Every set in this union contains xx. A union of connected sets sharing a common point is connected, so C(x)C(x) is itself connected. It contains every connected subset containing xx, which establishes its maximality.

Here, maximal means that the subset cannot be enlarged while remaining connected. It does not mean that the component has the largest cardinality, diameter, or measure among all components.

Partition into components

If two connected subsets intersect, their union is connected. Consequently, two connected components that intersect must coincide.

Thus, the components form a partition of XX: every point belongs to exactly one component. Equivalently, the relation

x∼y⟺some connected subset of X contains both x and yx\sim y \quad\Longleftrightarrow\quad \text{some connected subset of }X\text{ contains both }x\text{ and }y

is an equivalence relation, and its equivalence classes are precisely the connected components.

A nonempty space is connected exactly when it has one component. The empty space has no components, although it is conventionally considered connected.

Closedness and openness

Every connected component is a closed subset of the ambient space. This follows because the closure of a connected set is connected; maximality therefore forces a component to equal its closure.

Components need not be open. In the rational numbers with the topology inherited from the real line, every component is a singleton, but no singleton is open. Given distinct rational numbers p<qp<q, an irrational number between them separates any subset containing both into two relatively open, nonempty parts.

If a space has finitely many components, each component is both open and closed: its complement is a finite union of closed components. Components are also open in every locally connected space, meaning a space in which each point has a neighborhood basis of connected open sets.

Examples

  • An interval in the real line is connected and therefore has exactly one component.
  • The subspace (−2,−1)∪(1,2)(-2,-1)\cup(1,2) has two components, namely the two intervals.
  • In a discrete space, every singleton is a component.
  • Every connected subset of the Cantor set is a singleton, so its components are individual points, despite the set being uncountable.

A space whose components are all singletons is called totally disconnected. This does not imply that the topology is discrete.

Connected components and path components

A path-connected space is one in which any two points can be joined by a continuous path. A path from xx to yy is a continuous map

γ:[0,1]⟶X,γ(0)=x,γ(1)=y.\gamma:[0,1]\longrightarrow X, \qquad \gamma(0)=x,\quad \gamma(1)=y.

A path component is a maximal path-connected subset.

Every path-connected space is connected, because continuous images of connected spaces are connected. Hence every path component lies within a connected component. The converse fails: a connected component may contain several path components.

A standard example is the closed topologist’s sine curve,

T={(x,sin⁡(1/x)):0<x≤1}∪({0}×[−1,1]).T= \{(x,\sin(1/x)):0<x\leq 1\} \cup \bigl(\{0\}\times[-1,1]\bigr).

The oscillating graph is connected, and its closure is TT, so TT is connected. Nevertheless, no path in TT joins the vertical segment at x=0x=0 to the oscillating graph. Thus TT has one connected component but two path components.

In a locally path-connected space, connected components and path components coincide and are open. This applies to manifolds and open subsets of Euclidean space. It explains why the distinction is often invisible in elementary geometric examples.

Connected components of graphs

For an undirected graph G=(V,E)G=(V,E), two vertices belong to the same component exactly when a finite graph path joins them. A path of length zero joins a vertex to itself, so an isolated vertex constitutes a component.

The component containing a vertex consists of all vertices reachable from it, together with all edges of GG between those vertices. No edge joins different components: such an edge would provide a path connecting them.

This definition applies to finite and infinite graphs. An infinite graph is connected if every pair of vertices is joined by a finite path; a single path visiting every vertex is not required.

Computing components

For a finite graph represented by adjacency lists, all components can be found by repeatedly exploring from an unvisited vertex:

  1. Select an unvisited vertex and assign it a new component label.
  2. Use breadth-first search or depth-first search to visit and label every reachable vertex.
  3. Repeat until every vertex has been visited.

Each vertex and edge is processed a bounded number of times, giving running time

O(∣V∣+∣E∣),O(|V|+|E|),

using big-O notation. With an adjacency-matrix representation, scanning for neighbors generally takes O(∣V∣2)O(|V|^2) time.

A disjoint-set data structure, also called union–find, offers another approach. Starting with one set per vertex, it merges the sets containing the endpoints of each edge. This is particularly useful when edges are added incrementally. Edge deletion requires additional machinery because removing an edge may split an existing component.

Directed graphs

For a directed graph, two distinct notions are important:

  • A weakly connected component is a component of the undirected graph obtained by ignoring edge directions.
  • A strongly connected component is a maximal set of vertices such that every vertex is reachable from every other vertex by a directed path.

Strong components partition the vertices. Contracting each strong component to one vertex and retaining edges between different components produces a directed acyclic graph, called the condensation graph.

Algebraic and topological descriptions

Graph matrices

If the vertices of a finite undirected graph are ordered component by component, its adjacency matrix becomes block diagonal. Each diagonal block describes one component, and entries between blocks are zero.

The graph Laplacian gives an algebraic way to count components. For an unweighted undirected graph,

L=D−A,L=D-A,

where AA is the adjacency matrix and DD is the diagonal matrix of vertex degrees. For a real vector zz,

zTLz=∑{u,v}∈E(zu−zv)2.z^{\mathsf T}Lz = \sum_{\{u,v\}\in E}(z_u-z_v)^2.

Thus Lz=0Lz=0 exactly when zz is constant on each component. The null space therefore has one independent direction per component, and

number of components=dim⁡ker⁡L.\text{number of components}=\dim\ker L.

Equivalently, the multiplicity of the eigenvalue zero equals the number of components.

Component spaces and homology

The set of connected components can be given the quotient topology induced by the map

q:X⟶Comp⁡(X),q(x)=C(x).q:X\longrightarrow \operatorname{Comp}(X), \qquad q(x)=C(x).

This constructs a quotient space by collapsing each connected component to a point. The resulting space need not be discrete, since components need not be open.

In algebraic topology, the notation π0(X)\pi_0(X) conventionally denotes the set of path components, not necessarily connected components. Likewise, zeroth singular homology is the free abelian group on the path components. These constructions count connected components when connected components and path components coincide, but the distinction matters for general spaces.

Applications and dependence on the model

Component decomposition separates problems into independent pieces. A graph calculation with no interactions between components can often be performed separately on each component. In network models, components describe groups mutually reachable under the chosen connection rule.

In digital image analysis, connected-component labeling groups foreground pixels or voxels according to a specified adjacency relation. In a square pixel grid, allowing only edge-sharing neighbors gives 4-connectivity; also allowing corner-sharing neighbors gives 8-connectivity. Two diagonally touching pixels may therefore belong to different components under one rule and the same component under another.

Similarly, in cluster analysis, connecting data points whose distance falls below a threshold produces clusters defined by graph components. Such clusters depend on the distance, threshold, and edge rule. A chain of short links may join points that are far apart, because connectedness requires reachability rather than uniformly small pairwise distances.