Start a depth-first search from each as-yet unlabelled vertex, propagating a fresh component number:
component = 0
for u in V:
    cc[u] = UNLABELLED
for u in V:
    if cc[u] == UNLABELLED:
        visit(u, component)
        component = component + 1

visit(u, label):
    cc[u] = label
    for v in adjacency[u]:
        if cc[v] == UNLABELLED:
            visit(v, label)
A search follows only edges, so every vertex it labels is reachable from its root. Conversely, if a reachable vertex remained unlabelled, a path to it would contain a first edge from a visited vertex to an unvisited one; scanning that edge would visit the latter, a contradiction. Thus each search labels exactly one connected component, proving both directions of the required equivalence.
Test Find-Set(u) == Find-Set(v). Initially the sets are singleton connected components of the edgeless graph; processing an edge joins precisely the components it connects. By induction over the processed edges, the final sets are exactly the connected components of .
True. Delete ; the resulting two connected components define a cut of a graph. If a crossing edge had , the exchange would be a spanning tree of smaller total weight, contradicting the minimum spanning tree assumption. Thus is a light edge crossing a cut for this fundamental cut. It need not be uniquely light.
Let be the indicator that black bead belongs to the white bead's connected component. The number of such black beads is . By linearity of expectation, no independence between these indicators is needed.
For , the six oriented distances give respective probabilities
Their sum is , the expected number of black beads in the white component. As a check, summing the formula from (i) and using gives the general value , again equal to when .
Path component Created 2026-09-24 Updated 2026-10-14
A path component of a topological space is a nonempty subset maximal among its path-connected subsets. The path component through can be described as
Every point along such a continuous path also belongs to : the initial part of the path reaches that point. Thus the paths witnessing membership stay inside . This makes path components useful for deciding which allowed positions can be reached from one another by continuous motion.
Every path component lies inside one connected component, because every path-connected space is connected. Thus each connected component is a union of path components. In a locally path-connected space the two classifications agree, by connected locally path-connected spaces are path-connected. For a subset of the real line with its usual subspace topology, the classifications also agree: every connected component is a real interval, and interpolation supplies a continuous path within it.
The topologist's sine curve shows why the distinction matters in general. Use specifically the closed version
with the subspace topology from the usual Euclidean plane. It has one connected component, , but two path components, and . The graph of a function is a continuous image of a connected space, and its closure is , so closure of a connected set gives connectedness. Each of is path-connected, but a continuous path crossing from into would force its second coordinate to oscillate between and arbitrarily near its departure time, contradicting continuity; the topologist's sine curve article gives the short argument. Also is not closed in , so path components need not be closed, unlike connected components.[ref]
Being joined by a continuous path is an equivalence relation. Proof outline: the constant path joins a point to itself; reverses a path; and a path from to followed by one from to gives a path from to . For the last construction, run each path on half of ; their values agree at , so the pasting lemma for closed subspaces gives continuity. The equivalence classes are path-connected, are maximal, and form a partition of a set of into path components.[ref]
Punctured ball 2026-10-25
A punctured ball is an open ball with its centre removed. In the real line it has two connected components. In Euclidean space of dimension it is path-connected: for any two points, choose a third point inside the ball outside the two lines through the centre and those points. Such a point exists since two lines do not cover an open ball in dimension at least two. The two line segments joining through that point stay inside the ball, which is a convex set, and avoid its centre. They form a continuous path.
Quasicomponent 2026-10-31
The quasicomponent of a point is the intersection of all its clopen neighborhoods. Every connected set containing the point lies in its quasicomponent, since a clopen set cannot split a connected set. In a compact Hausdorff space, quasicomponents equal connected components by the Šura-Bura component lemma.
Quasi-component 2026-10-31
The quasi-component of a point is the intersection of its clopen neighborhoods. Its connected component is always contained in it: a connected set meeting a clopen set cannot also meet its complement. Equality need not hold in noncompact Hausdorff spaces. The Šura-Bura lemma proves equality in compact Hausdorff spaces.
Random cuts of a cycle 2026-10-25
Choose distinct edges uniformly from an -vertex cycle graph, with , and delete them. Two specified vertices at oriented distance remain connected exactly when one of their two complementary edge-disjoint paths is uncut. All cuts must then lie in the other path, giving the displayed probability. The two events are disjoint because at least one edge is cut. Set when .
Summing the connectivity indicators for all other vertices gives an expected number
of other vertices in a tagged connected component. The sum identity follows by classifying -element subsets according to their greatest element. For three cuts this is other vertices.
The rank of a vector bundle is locally constant on the base. Taking the difference of the ranks extends to the Grothendieck group of vector bundles, giving the rank map in Topological K-theory. For a finite CW complex, its kernel consists of classes of rank zero on every connected component.
Reciprocal rescaling symmetry of two cross-coupled scalar fields Created 2026-10-18 Updated 2026-11-05
For , the real linear internal transformations preserving the density are and with . There are four connected components; the identity component is the displayed reciprocal rescaling with . In the sum-and-difference basis it preserves a bilinear form of signature , with the identity component isomorphic to that of the One-dimensional Lorentz group. Its Noether current in coordinates is and . The two wave equations give . The energy quadratic form is indefinite: the fields have equal and opposite kinetic signs.
Smooth function with a pointwise vanishing derivative Created 2026-09-24 Updated 2026-11-05
If and every has some nonnegative integer with , then is a polynomial. The derivative order may vary with ; there is no assumed uniform bound.[ref]
Let be the open set where is locally a polynomial. The closed sets cover . Applying the Baire category theorem on every closed interval shows that is dense. Overlapping polynomials agree, so each connected component of carries one polynomial.
If were nonempty, it would be closed with no isolated points: adjacent polynomials at an isolated point have matching derivatives and glue across it. Apply the Baire category theorem on to find an open interval with . Taking derivatives along accumulation points gives on for all . Every intervening polynomial component has an endpoint there; matching its derivatives forces its degree below . Hence throughout , contradicting . Thus , and overlapping local polynomials give one global polynomial.
Southern Oscillation 2026-11-05
The Southern Oscillation is a large-scale variation of tropical atmospheric pressure and circulation, associated with the coupled El Niño–Southern Oscillation. Its pressure pattern is commonly monitored through the contrast between the eastern and western tropical Pacific.
Changes in trade winds affect ocean upwelling and surface temperatures; those temperature changes can feed back on convection and pressure. The atmospheric oscillation and the oceanic El Niño pattern are therefore connected components of a coupled system. A pressure index is an observational summary, not a complete dynamical model of the phenomenon.
Spanning forest 2026-10-20
An acyclic spanning subgraph containing a spanning tree of each connected component of the original graph. For a graph with vertices and components, a spanning forest has edges.
Spectral graph theory Created 2026-10-14 Updated 2026-11-05
Spectral graph theory studies a graph through eigenvalues and eigenvectors of associated matrices, especially its adjacency matrix and graph Laplacian. A graph eigenvalue usually means an adjacency eigenvalue unless another matrix is specified.
For an undirected graph, the Laplacian satisfies . Its kernel therefore consists of vectors constant on each connected component, so the multiplicity of zero equals the number of components. This makes a discrete connectivity property visible in linear algebra. Nonzero eigenvalues further quantify mixing, expansion, and the cost of varying across edges.
For , the contracted Bianchi identity and the commutation identity imply . Meanwhile , so their sum is constant on every connected component.
In a compact Hausdorff space, the quasicomponent is connected and equals the connected component of . If were a nontrivial separation, disjoint open neighborhoods of its compact pieces leave a compact complement missing . Finitely many clopen neighborhoods of intersect to a clopen containing inside . The piece is then clopen in the whole space, contains , and misses the nonempty other piece, contradicting the definition of . This also proves that any neighborhood of a component contains a clopen neighborhood of that component, by compactness of its complement.
Šura-Bura lemma 2026-10-31
In a compact Hausdorff space, each connected component is its quasi-component and has a neighborhood basis of clopen sets. Let be the intersection of clopen neighborhoods of . It is compact. If it splits into two nonempty compact sets, normality separates them by disjoint open neighborhoods. The finite intersection characterization of compactness gives a finite intersection of clopen neighborhoods lying in their union. Its intersection with the neighborhood containing is then clopen and excludes part of , a contradiction. Thus is connected and equals the component. Applying the same finite-intersection argument to any neighborhood of proves the neighborhood-basis assertion. [ref].
A compact Lie group has finitely many connected components, each an oriented compact manifold of dimension . Componentwise integration identifies its top-degree de Rham cohomology with one real coordinate per component. For a connected group, if top-degree classes are represented by invariant forms, the invariant volume form on a Lie group spans the cohomology: invariant top forms are one-dimensional, and its positive integral proves that its class is nonzero by the Generalized Stokes theorem. A disconnected group cannot have an invariant representative of every top-degree class, since left translations permute its components. For example, has two independent degree-one classes but only one independent invariant top form.