graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a component of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is a

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into

disjoint set In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A c ...

s, and are the

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

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 Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

, and is closely related to invariants of

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...

s, and

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

. In

random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...

s, a frequently occurring phenomenon is the incidence of a

giant component In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices. Giant component in Erdős–Rényi model Giant components are a prominent feature of the Erd� ...

, one component that is significantly larger than the others; and of a

percolation threshold The percolation threshold is a mathematical concept in percolation theory that describes the formation of long-range connectivity in random systems. Below the threshold a giant connected component does not exist; while above it, there exists a ...

, 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, and a special case of the problem,

connected-component labeling Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, or region extraction is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled ...

, is a basic technique in image analysis.

Dynamic connectivity In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph. The set ''V'' of vertices of the graph is fixed, but the set ''E'' of edges can ch ...

algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, connected components have been used to study algorithms with limited

space complexity The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it ex ...

, and sublinear time algorithms can accurately estimate the number of components.

Definitions and examples

A component of a given undirected graph may be defined as a connected subgraph that is not part of any larger connected subgraph. For instance, the graph shown in the first illustration has three components. Every vertex

v

of a graph belongs to one of the graph's components, which may be found as the

of the set of vertices reachable from Every graph is the

disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ( ...

of its components. Additional examples include the following special cases: *In an

empty graph In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is th ...

, each vertex forms a component with one vertex and zero edges. More generally, a component of this type is formed for every

isolated vertex In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of ver ...

in any graph. *In a

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

, there is exactly one component: the whole graph. *In a

forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

, every component is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

. *In a

cluster graph In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster ...

, every component is a

maximal clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is compl ...

. These graphs may be produced as the

transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...

s of arbitrary undirected graphs, for which finding the transitive closure is an equivalent formulation of identifying the connected components. Another definition of components involves the equivalence classes of an equivalence relation defined on the graph's vertices. In an undirected graph, a is ''reachable'' from a if there is a

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...

from

u

or equivalently a

walk Walking (also known as ambulation) is one of the main gaits of terrestrial locomotion among legged animals. Walking is typically slower than running and other gaits. Walking is defined by an ' inverted pendulum' gait in which the body vaults ...

(a path allowing repeated vertices and edges). Reachability is an equivalence relation, since: *It is reflexive: There is a trivial path of length zero from any vertex to itself. *It is

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

: If there is a path from

u

the same edges in the reverse order form a path from

v

*It is transitive: If there is a path from

u

and a path from

v

the two paths may be concatenated together to form a walk from

u

The

equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...

es of this relation partition the vertices of the graph into

disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...

, subsets of vertices that are all reachable from each other, with no additional reachable pairs outside of any of these subsets. Each vertex belongs to exactly one equivalence class. The components are then the

s formed by each of these equivalence classes. Alternatively, some sources define components as the sets of vertices rather than as the subgraphs they induce. Similar definitions involving equivalence classes have been used to defined components for other forms of graph

connectivity Connectivity may refer to: Computing and technology * Connectivity (media), the ability of the social media to accumulate economic capital from the users connections and activities * Internet connectivity, the means by which individual terminal ...

, including the weak components and strongly connected components of

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

s and the

biconnected component In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...

s of undirected graphs.

Number of components

The number of components of a given finite graph can be used to count the number of edges in its

spanning forest In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

s: In a graph with

n

vertices and

c

components, every spanning forest will have exactly

n-c

edges. This number

n-c

is the

-theoretic

rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * ...

of the graph, and the

of its

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...

. The rank of the dual cographic matroid equals the

circuit rank In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...

of the graph, the minimum number of edges that must be removed from the graph to break all its cycles. In a graph with

m

edges,

n

vertices and

c

components, the circuit rank is A graph can be interpreted as a

in multiple ways, for instance by placing its vertices as points in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that ar ...

in three-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

and representing its edges as line segments between those points. The components of a graph can be generalized through these interpretations as the topological connected components of the corresponding space; these are equivalence classes of points that cannot be separated by pairs of disjoint closed sets. Just as the number of connected components of a topological space is an important

topological invariant In topology and related areas of mathematics, a topological property or topological invariant is a property of a topological space that is invariant under homeomorphisms. Alternatively, a topological property is a proper class of topological space ...

, the zeroth

Betti number In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of ''n''-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (such as compact manifolds, finite simplicia ...

, the number of components of a graph is an important

, and in

topological graph theory In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in ...

it can be interpreted as the zeroth Betti number of the graph. The number of components arises in other ways in graph theory as well. In

algebraic graph theory Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph th ...

it equals the multiplicity of 0 as an

eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

of the Laplacian matrix of a finite graph. It is also the index of the first nonzero coefficient of the

chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...

of the graph, and the chromatic polynomial of the whole graph can be obtained as the product of the polynomials of its components. Numbers of components play a key role in the

Tutte theorem In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs ...

characterizing finite graphs that have

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...

s and the associated

Tutte–Berge formula In the mathematical discipline of graph theory the Tutte–Berge formula is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte theorem on perfect matchings, and is named after W. T. Tutte (who pro ...

for the size of a

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...

, and in the definition of

graph toughness Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

Algorithms

It is straightforward to compute the components of a finite graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...

or depth-first search. In either case, a search that begins at some particular will find the entire component (and no more) before returning. All components of a graph can be found by looping through its vertices, starting a new breadth-first or depth-first search whenever the loop reaches a vertex that has not already been included in a previously found component. describe essentially this algorithm, and state that it was already "well known".

Connected-component labeling Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, or region extraction is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled ...

, a basic technique in computer image analysis, involves the construction of a graph from the image and component analysis on the graph. The vertices are the subset of the

pixel In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device. In most digital display devices, pixels are the ...

s of the image, chosen as being of interest or as likely to be part of depicted objects. Edges connect adjacent pixels, with adjacency defined either orthogonally according to the

Von Neumann neighborhood In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, ...

, or both orthogonally and diagonally according to the

Moore neighborhood In cellular automata, the Moore neighborhood is defined on a two-dimensional square lattice and is composed of a central cell and the eight cells that surround it. Name The neighborhood is named after Edward F. Moore, a pioneer of cellular aut ...

. Identifying the connected components of this graph allows additional processing to find more structure in those parts of the image or identify what kind of object is depicted. Researchers have developed component-finding algorithms specialized for this type of graph, allowing it to be processed in pixel order rather than in the more scattered order that would be generated by breadth-first or depth-first searching. This can be useful in situations where sequential access to the pixels is more efficient than random access, either because the image is represented in a hierarchical way that does not permit fast random access or because sequential access produces better

memory access pattern In computing, a memory access pattern or IO access pattern is the pattern with which a system or program reads and writes memory on secondary storage. These patterns differ in the level of locality of reference and drastically affect cache performa ...

s. There are also efficient algorithms to dynamically track the components of a graph as vertices and edges are added, by using a

disjoint-set data structure In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set ...

to keep track of the partition of the vertices into equivalence classes, replacing any two classes by their union when an edge connecting them is added. These algorithms take

amortized In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case ...

time

O(\alpha(n))

per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and

\alpha

is a very slowly growing inverse of the very quickly growing Ackermann function. One application of this sort of incremental connectivity algorithm is in Kruskal's algorithm for

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

s, which adds edges to a graph in sorted order by length and includes an edge in the minimum spanning tree only when it connects two different components of the previously-added subgraph. When both edge insertions and edge deletions are allowed,

dynamic connectivity In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph. The set ''V'' of vertices of the graph is fixed, but the set ''E'' of edges can ch ...

algorithms can still maintain the same information, in amortized time

O(\log^2 n/\log\log n)

per change and time

O(\log n/\log\log n)

per connectivity query, or in near-logarithmic randomized

expected time In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case com ...

. Components of graphs have been used in

to study the power of

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

s that have a working memory limited to a

logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...

ic number of bits, with the much larger input accessible only through read access rather than being modifiable. The problems that can be solved by machines limited in this way define the

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...

L. It was unclear for many years whether connected components could be found in this model, when formalized as a

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...

of testing whether two vertices belong to the same component, and in 1982 a related complexity class, SL, was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space reductions. It was finally proven in 2008 that this connectivity problem can be solved in logarithmic space, and therefore that In a graph represented as an

adjacency list In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is ...

, with random access to its vertices, it is possible to estimate the number of connected components, with constant probability of obtaining additive (absolute) error at most

\varepsilon n

, in sublinear time

O(\varepsilon^\log\varepsilon^)

In random graphs

s the sizes of components are given by a

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...

, which, in turn, depends on the specific model of how random graphs are chosen. In the

G(n, p)

version of the Erdős–Rényi–Gilbert model, a graph on

n

vertices is generated by choosing randomly and independently for each pair of vertices whether to include an edge connecting that pair, with of including an edge and probability

1-p

of leaving those two vertices without an edge connecting them. The connectivity of this model depends and there are three different ranges with very different behavior from each other. In the analysis below, all outcomes occur

with high probability In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number ''n'' and goes to 1 as ''n'' goes to infinity, i.e. the probability of the event occurring can be ma ...

, meaning that the probability of the outcome is arbitrarily close to one for sufficiently large values The analysis depends on a parameter

\varepsilon

, a positive constant independent of

n

that can be arbitrarily close to zero. ;Subcritical

p < (1-\varepsilon)/n

: In this range of

p

, all components are simple and very small. The largest component has logarithmic size. The graph is a

pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...

. Most of its components are trees: the number of vertices in components that have cycles grows more slowly than any unbounded function of the number of vertices. Every tree of fixed size occurs linearly many times. ;Critical

p \approx 1/n

: The largest connected component has a number of vertices proportional to There may exist several other large components; however, the total number of vertices in non-tree components is again proportional to ;Supercritical

p >(1+\varepsilon)/n

: There is a single

containing a linear number of vertices. For large values of

p

its size approaches the whole graph:

, C_1,  \approx yn

where

y

is the positive solution to the equation The remaining components are small, with logarithmic size. In the same model of random graphs, there will exist multiple connected components with high probability for values of

p

below a significantly higher threshold, and a single connected component for values above the threshold, This phenomenon is closely related to the

coupon collector's problem In probability theory, the coupon collector's problem describes "collect all coupons and win" contests. It asks the following question: If each box of a brand of cereals contains a coupon, and there are ''n'' different types of coupons, what is th ...

: in order to be connected, a random graph needs enough edges for each vertex to be incident to at least one edge. More precisely, if random edges are added one by one to a graph, then with high probability the first edge whose addition connects the whole graph touches the last isolated vertex. For different models including the random subgraphs of grid graphs, the connected components are described by

percolation theory In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnecte ...

. A key question in this theory is the existence of a

, a critical probability above which a giant component (or infinite component) exists and below which it does not.

References

{{reflist, refs= {{citation , last1 = Clark , first1 = John , last2 = Holton , first2 = Derek Allan , isbn = 9788170234630 , page = 28 , publisher = Allied Publishers , title = A First Look at Graph Theory , url = https://books.google.com/books?id=kb-aLlgYZuEC&pg=PA28 , year = 1995 {{citation , last = Bengelloun , first = Safwan Abdelmajid , date = December 1982 , id = {{ProQuest, 303248045 , page = 12 , publisher = Yale University , title = Aspects of Incremental Computing , type = PhD thesis {{citation , last = Berge , first = Claude , author-link = Claude Berge , journal = Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences , mr = 100850 , pages = 258–259 , title = Sur le couplage maximum d'un graphe , volume = 247 , year = 1958 {{citation , last1 = Berenbrink , first1 = Petra , last2 = Krayenhoff , first2 = Bruce , last3 = Mallmann-Trenn , first3 = Frederik , doi = 10.1016/j.ipl.2014.05.008 , issue = 11 , journal =

Information Processing Letters ''Information Processing Letters'' is a peer reviewed scientific journal in the field of computer science, published by Elsevier Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its ...

, mr = 3230913 , pages = 639–642 , title = Estimating the number of connected components in sublinear time , volume = 114 , year = 2014 {{citation , last = Bollobás , first = Béla , author-link = Béla Bollobás , doi = 10.1007/978-1-4612-0619-4 , isbn = 0-387-98488-7 , mr = 1633290 , page = 6 , publisher = Springer-Verlag , location = New York , series = Graduate Texts in Mathematics , title = Modern Graph Theory , url = https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA6 , volume = 184 , year = 1998 {{citation , last1 = Siek , first1 = Jeremy , last2 = Lee , first2 = Lie-Quan , last3 = Lumsdaine , first3 = Andrew , contribution = 7.1 Connected components: Definitions , pages = 97–98 , publisher = Addison-Wesley , title = The Boost Graph Library: User Guide and Reference Manual , year = 2001 {{citation , last = Chvátal , first = Václav , author-link = Václav Chvátal , doi = 10.1016/0012-365X(73)90138-6 , doi-access = free , issue = 3 , journal = Discrete Mathematics , mr = 0316301 , pages = 215–228 , title = Tough graphs and Hamiltonian circuits , volume = 5 , year = 1973 {{citation , last = Cioabă , first = Sebastian M. , editor-last = Dehmer , editor-first = Matthias , contribution = Some applications of eigenvalues of graphs , doi = 10.1007/978-0-8176-4789-6_14 , location = New York , mr = 2777924 , pages = 357–379 , publisher = Birkhäuser/Springer , title = Structural Analysis of Complex Networks , year = 2011; se
proof of Lemma 5, p. 361
/ref> {{citation , last1 = Cohen , first1 = Reuven , last2 = Havlin , first2 = Shlomo , contribution = 10.1 Percolation on complex networks: Introduction , contribution-url = https://books.google.com/books?id=1ECLiFrKulIC&pg=PA97 , isbn = 978-1-139-48927-0 , pages = 97–98 , publisher = Cambridge University Press , title = Complex Networks: Structure, Robustness and Function , year = 2010 {{citation , last1 = Dillencourt , first1 = Michael B. , last2 = Samet , first2 = Hanan , author2-link = Hanan Samet , last3 = Tamminen , first3 = Markku , doi = 10.1145/128749.128750 , issue = 2 , journal =

Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...

, mr = 1160258 , pages = 253–280 , title = A general approach to connected-component labeling for arbitrary image representations , volume = 39 , year = 1992 {{citation , last = Foldes , first = Stephan , isbn = 978-1-118-03143-8 , page = 199 , publisher = John Wiley & Sons , title = Fundamental Structures of Algebra and Discrete Mathematics , url = https://books.google.com/books?id=A59RivXPMzkC&pg=PA199 , year = 2011 {{citation , last1 = Frieze , first1 = Alan , author1-link = Alan M. Frieze , last2 = Karoński , first2 = Michał , contribution = 1.1 Models and relationships , doi = 10.1017/CBO9781316339831 , isbn = 978-1-107-11850-8 , mr = 3675279 , pages = 3–9 , publisher = Cambridge University Press, Cambridge , title = Introduction to Random Graphs , year = 2016 {{harvtxt, Frieze, Karoński, 2016, 2.1 Sub-critical phase, pp. 20–33; see especially Theorem 2.8, p. 26, Theorem 2.9, p. 28, and Lemma 2.11, p. 29 {{harvtxt, Frieze, Karoński, 2016, 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39 {{harvtxt, Frieze, Karoński, 2016, 2.3 Phase transition, pp. 39–45 {{harvtxt, Frieze, Karoński, 2016, 4.1 Connectivity, pp. 64–68 {{citation , last1 = Huang , first1 = Shang-En , last2 = Huang , first2 = Dawei , last3 = Kopelowitz , first3 = Tsvi , last4 = Pettie , first4 = Seth , editor-last = Klein , editor-first = Philip N. , arxiv = 1609.05867 , contribution = Fully dynamic connectivity in

O\bigl(\log n(\log\log n)^2\bigr)

amortized expected time , doi = 10.1137/1.9781611974782.32 , pages = 510–520 , title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , year = 2017 {{citation , last1 = Hopcroft , first1 = John , author1-link = John Hopcroft , last2 = Tarjan , first2 = Robert , author2-link = Robert Tarjan , date = June 1973 , doi = 10.1145/362248.362272 , issue = 6 , journal =

Communications of the ACM ''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are intended for readers with ...

, pages = 372–378 , title = Algorithm 447: efficient algorithms for graph manipulation , volume = 16 {{citation , last1 = Joyner , first1 = David , last2 = Nguyen , first2 = Minh Van , last3 = Phillips , first3 = David , contribution = 1.6.1 Union, intersection, and join , contribution-url = https://code.google.com/p/graphbook/ , date = May 10, 2013 , edition = 0.8-r1991 , pages = 34–35 , publisher = Google , title = Algorithmic Graph Theory and Sage {{citation , last = Knuth , first = Donald E. , author-link = Donald Knuth , contribution = Weak components , date = January 15, 2022 , pages = 11–14 , title = The Art of Computer Programming, Volume 4, Pre-Fascicle 12A: Components and Traversal , url = https://cs.stanford.edu/~knuth/fasc12a+.pdf {{citation , last = Kozen , first = Dexter C. , author-link = Dexter Kozen , contribution = 4.1 Biconnected components , contribution-url = https://books.google.com/books?id=HFn1BwAAQBAJ&pg=PA20 , doi = 10.1007/978-1-4612-4400-4 , isbn = 0-387-97687-6 , mr = 1139767 , pages = 20–22 , publisher = Springer-Verlag , location = New York , series = Texts and Monographs in Computer Science , title = The Design and Analysis of Algorithms , year = 1992 {{citation , last1 = Lewis , first1 = Harry R. , author1-link = Harry R. Lewis , last2 = Papadimitriou , first2 = Christos H. , author2-link = Christos Papadimitriou , doi = 10.1016/0304-3975(82)90058-5 , issue = 2 , journal =

Theoretical Computer Science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, mr = 666539 , pages = 161–187 , title = Symmetric space-bounded computation , volume = 19 , year = 1982 {{citation , last1 = Lewis , first1 = Harry , author1-link = Harry R. Lewis , last2 = Zax , first2 = Rachel , isbn = 978-0-691-19061-7 , page = 145 , publisher = Princeton University Press , title = Essential Discrete Mathematics for Computer Science , url = https://books.google.com/books?id=fAZ-DwAAQBAJ&pg=PA145 , year = 2019 {{citation , last1 = McColl , first1 = W. F. , last2 = Noshita , first2 = K. , doi = 10.1016/0166-218X(86)90020-X , issue = 1 , journal = Discrete Applied Mathematics , mr = 856101 , pages = 67–73 , title = On the number of edges in the transitive closure of a graph , volume = 15 , year = 1986 {{citation , last = Read , first = Ronald C. , author-link = Ronald C. Read , doi = 10.1016/S0021-9800(68)80087-0 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 224505 , pages = 52–71 , title = An introduction to chromatic polynomials , volume = 4 , year = 1968; see Theorem 2, p. 59, and corollary, p. 65 {{citation , last = Reingold , first = Omer , author-link = Omer Reingold , doi = 10.1145/1391289.1391291 , doi-access = free , issue = 4 , journal =

, mr = 2445014 , page = A17:1–A17:24 , title = Undirected connectivity in log-space , volume = 55 , year = 2008 {{citation , last = Skiena , first = Steven , author-link = Steven Skiena , contribution = 6.1.2 Kruskal's Algorithm , contribution-url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA196 , doi = 10.1007/978-1-84800-070-4 , isbn = 978-1-84800-069-8 , pages = 196–198 , publisher = Springer , title = The Algorithm Design Manual , year = 2008 {{citation , last1 = Thulasiraman , first1 = K. , last2 = Swamy , first2 = M. N. S. , isbn = 978-1-118-03025-7 , page = 9 , publisher = John Wiley & Sons , title = Graphs: Theory and Algorithms , url = https://books.google.com/books?id=rFH7eQffQNkC&pg=PA9 , year = 2011 {{citation , last = Tutte , first = W. T. , author-link = W. T. Tutte , isbn = 0-201-13520-5 , mr = 746795 , page = 15 , publisher = Addison-Wesley , location = Reading, Massachusetts , series = Encyclopedia of Mathematics and its Applications , title = Graph Theory , url = https://books.google.com/books?id=uTGhooU37h4C&pg=PA15 , volume = 21 , year = 1984 {{citation , last = Tutte , first = W. T. , author-link = W. T. Tutte , doi = 10.1112/jlms/s1-22.2.107 , journal = The Journal of the London Mathematical Society , mr = 23048 , pages = 107–111 , title = The factorization of linear graphs , volume = 22 , year = 1947 {{citation , last = Wilson , first = R. J. , author-link = Robin Wilson (mathematician) , doi = 10.1080/00029890.1973.11993318 , journal = The American Mathematical Monthly , jstor = 2319608 , mr = 371694 , pages = 500–525 , title = An introduction to matroid theory , volume = 80 , year = 1973 {{citation , last = Wood , first = David R. , author-link = David Wood (mathematician) , editor-last = Kao , editor-first = Ming-Yang , contribution = Three-dimensional graph drawing , doi = 10.1007/978-3-642-27848-8_656-1 , pages = 1–7 , publisher = Springer , title = Encyclopedia of Algorithms , url = https://users.monash.edu/~davidwo/papers/EncPaper.pdf , year = 2014 {{citation , last = Wulff-Nilsen , first = Christian , editor-last = Khanna , editor-first = Sanjeev , arxiv = 1209.5608 , contribution = Faster deterministic fully-dynamic graph connectivity , doi = 10.1137/1.9781611973105.126 , pages = 1757–1769 , title = Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 , year = 2013

External links

MATLAB code to find components in undirected graphs
MATLAB File Exchange.
Connected components
Steven Skiena, The Stony Brook Algorithm Repository Graph connectivity Graph theory objects