Editing Component (graph theory)

{{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.

==Definitions and examples==
[[File:Equivalentie.svg|thumb|A [[cluster graph]] with seven components]]
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 <math>v</math> of a graph belongs to one of the graph's components, which may be found as the [[induced subgraph]] of the set of vertices [[reachability|reachable]] from {{nowrap|<math>v</math>.{{r|1look}}}} Every graph is the [[Disjoint union of graphs|disjoint union]] of its components.{{r|jnp}} Additional examples include the following special cases:
*In an [[empty graph]], each vertex forms a component with one vertex and zero edges.{{r|tutte-betti}} More generally, a component of this type is formed for every [[isolated vertex]] in any graph.{{r|thuswa}}
*In a [[connected graph]], there is exactly one component: the whole graph.{{r|thuswa}}
*In a [[forest (graph theory)|forest]], every component is a [[tree (graph theory)|tree]].{{r|bollobas}}
*In a [[cluster graph]], every component is a [[maximal clique]]. These graphs may be produced as the [[transitive closure]]s of arbitrary undirected graphs, for which finding the transitive closure is an equivalent formulation of identifying the connected components.{{r|mcnosh}}

Another definition of components involves the equivalence classes of an [[equivalence relation]] defined on the graph's vertices.
In an undirected graph, a {{nowrap|vertex <math>v</math>}} is ''reachable'' from a {{nowrap|vertex <math>u</math>}} if there is a [[Path (graph theory)|path]] from <math>u</math> {{nowrap|to <math>v</math>,}} or equivalently a [[Walk (graph theory)|walk]] (a path allowing repeated vertices and edges).
Reachability is an equivalence relation, since:
*It is [[reflexive relation|reflexive]]: There is a trivial path of length zero from any vertex to itself.
*It is [[symmetric relation|symmetric]]: If there is a path from <math>u</math> {{nowrap|to <math>v</math>,}} the same edges in the reverse order form a path from <math>v</math> {{nowrap|to <math>u</math>.}}
*It is [[Transitive relation|transitive]]: If there is a path from <math>u</math> {{nowrap|to <math>v</math>}} and a path from <math>v</math> {{nowrap|to <math>w</math>,}} the two paths may be concatenated together to form a walk from <math>u</math> {{nowrap|to <math>w</math>.}}
The [[equivalence class]]es of this relation partition the vertices of the graph into [[disjoint sets]], 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 [[induced subgraph]]s formed by each of these equivalence classes.{{r|foldes}} Alternatively, some sources define components as the sets of vertices rather than as the subgraphs they induce.{{r|boost}}

Similar definitions involving equivalence classes have been used to defined components for other forms of graph [[Connectivity (graph theory)|connectivity]], including the [[weak component]]s{{r|knuth}} and [[strongly connected component]]s of [[directed graph]]s{{r|lewzax}} and the [[biconnected component]]s of undirected graphs.{{r|kozen}}

==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]]s: In a graph with <math>n</math> vertices and <math>c</math> components, every spanning forest will have exactly <math>n-c</math> edges. This number <math>n-c</math> is the [[matroid]]-theoretic [[Rank (graph theory)|rank]] of the graph, and  the [[matroid rank|rank]] of its [[graphic matroid]]. The rank of the [[dual matroid|dual cographic matroid]] equals the [[circuit rank]] of the graph, the minimum number of edges that must be removed from the graph to break all its cycles. In a graph with <math>m</math> edges, <math>n</math> vertices and <math>c</math> components, the circuit rank is {{nowrap|<math>m-n+c</math>.{{r|wilson}}}}

A graph can be interpreted as a [[topological space]] in multiple ways, for instance by placing its vertices as points in [[general position]] in three-dimensional [[Euclidean space]] and representing its edges as line segments between those points.{{r|wood}} The components of a graph can be generalized through these interpretations as the [[Connected component (topology)|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]], the zeroth [[Betti number]], the number of components of a graph is an important [[graph invariant]], and in [[topological graph theory]] it can be interpreted as the zeroth Betti number of the graph.{{r|tutte-betti}}

The number of components arises in other ways in graph theory as well. In [[algebraic graph theory]] it equals the multiplicity of 0 as an [[eigenvalue]] of the [[Laplacian matrix]] of a finite graph.{{r|cioaba}} It is also the index of the first nonzero coefficient of the [[chromatic polynomial]] of the graph, and the chromatic polynomial of the whole graph can be obtained as the product of the polynomials of its components.{{r|read}} Numbers of components play a key role in the [[Tutte theorem]] characterizing finite graphs that have [[perfect matching]]s{{r|tutte-matching}} and the associated [[Tutte–Berge formula]] for the size of a [[maximum matching]],{{r|berge}} and in the definition of [[graph toughness]].{{r|chvatal}}

==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]] or [[depth-first search]]. In either case, a search that begins at some particular {{nowrap|vertex <math>v</math>}} will find the entire component {{nowrap|containing <math>v</math>}} (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.  {{harvtxt|Hopcroft|Tarjan|1973}} describe essentially this algorithm, and state that it was already "well known".{{r|hoptar}}

[[Connected-component labeling]], 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]]s of the image, chosen as being of interest or as likely to be part of depicted objects. Edges connect [[pixel connectivity|adjacent pixels]], with adjacency defined either orthogonally according to the [[Von Neumann neighborhood]], or both orthogonally and diagonally according to the [[Moore neighborhood]]. 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]]s.{{r|dst}}

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]] 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 analysis|amortized]] time <math>O(\alpha(n))</math> per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and <math>\alpha</math>  is a very slowly growing inverse of the very quickly growing [[Ackermann function]].{{r|bengalloun}} One application of this sort of incremental connectivity algorithm is in [[Kruskal's algorithm]] for [[minimum spanning tree]]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.{{r|skiena}} When both edge insertions and edge deletions are allowed, [[dynamic connectivity]] algorithms can still maintain the same information, in amortized time <math>O(\log^2 n/\log\log n)</math> per change and time <math>O(\log n/\log\log n)</math> per connectivity query,{{r|wulff-nilsen}} or in near-logarithmic randomized [[expected time]].{{r|hhkp}}

Components of graphs have been used in [[computational complexity theory]] to study the power of [[Turing machine]]s that have a working memory limited to a [[logarithm]]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]] [[L (complexity)|L]]. It was unclear for many years whether connected components could be found in this model, when formalized as a [[decision problem]] of testing whether two vertices belong to the same component, and in 1982 a related complexity class, [[SL (complexity)|SL]], was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space [[Reduction (complexity)|reductions]].{{r|lewpap}} It was finally proven in 2008 that this connectivity problem can be solved in logarithmic space, and therefore that {{nowrap|SL {{=}} L.{{r|reingold}}}}

In a graph represented as an [[adjacency list]], with random access to its vertices, it is possible to estimate the number of connected components, with constant probability of obtaining [[absolute error|additive (absolute) error]] at most <math>\varepsilon n</math>, in [[sublinear time]] <math>O(\varepsilon^{-2}\log\varepsilon^{-1})</math>.{{r|berkramal}}

== In random graphs ==
{{main|Giant component}}
[[File:Critical 1000-vertex Erdős–Rényi–Gilbert graph.svg|thumb|An [[Erdős–Rényi model|Erdős–Rényi–Gilbert random graph]] with 1000 vertices with edge probability <math>p=1/(n-1)</math> (in the critical range), showing a large component and many small ones]]
In [[random graph]]s the sizes of components are given by a [[random variable]], which, in turn, depends on the specific model of how random graphs are chosen. 
In the <math>G(n, p)</math> version of the [[Erdős–Rényi model|Erdős–Rényi–Gilbert model]], a graph on <math>n</math> vertices is generated by choosing randomly and independently for each pair of vertices whether to include an edge connecting that pair, with {{nowrap|probability <math>p</math>}} of including an edge and probability <math>1-p</math> of leaving those two vertices without an edge connecting them.{{r|frikar}} The connectivity of this model depends {{nowrap|on <math>p</math>,}} and there are three different ranges {{nowrap|of <math>p</math>}} with very different behavior from each other. In the analysis below, all outcomes occur [[with high probability]], meaning that the probability of the outcome is arbitrarily close to one for sufficiently large values {{nowrap|of <math>n</math>.}} The analysis depends on a parameter <math>\varepsilon</math>, a positive constant independent of <math>n</math> that can be arbitrarily close to zero.

;Subcritical <math>p < (1-\varepsilon)/n</math>
: In this range of <math>p</math>, all components are simple and very small. The largest component has logarithmic size. The graph is a [[pseudoforest]]. 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.{{r|subcritical}}
;Critical <math>p \approx 1/n</math>
: The largest connected component has a number of vertices proportional to {{nowrap|<math>n^{2/3}</math>.}} There may exist several other large components; however, the total number of vertices in non-tree components is again proportional to {{nowrap|<math>n^{2/3}</math>.{{r|critical}}}}
;Supercritical <math>p >(1+\varepsilon)/n</math>
: There is a single [[giant component]] containing a linear number of vertices. For large values of <math>p</math> its size approaches the whole graph: <math>|C_1| \approx yn</math> where <math>y</math> is the positive solution to the equation {{nowrap|<math>e^{-p n y }=1-y</math>.}} The remaining components are small, with logarithmic size.{{r|supercritical}}
In the same model of random graphs, there will exist multiple connected components with high probability for values of <math>p</math> below a significantly higher threshold, {{nowrap|<math>p<(1-\varepsilon)(\log n)/n</math>,}} and a single connected component for values above the threshold, {{nowrap|<math>p>(1+\varepsilon)(\log n)/n</math>.}} This phenomenon is closely related to the [[coupon collector's problem]]: 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.{{r|random-connectivity}}

For different models including the random subgraphs of grid graphs, the connected components are described by [[percolation theory]]. A key question in this theory is the existence of a [[percolation threshold]], a critical probability above which a giant component (or infinite component) exists and below which it does not.{{r|cohav}}

==References==
{{reflist|refs=

<ref name=1look>{{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
 | access-date = 2022-01-07
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108225127/https://books.google.com/books?id=kb-aLlgYZuEC&pg=PA28
 | url-status = live
 }}</ref>

<ref name=bengalloun>{{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}}</ref>

<ref name=berge>{{citation
 | last = Berge | first = Claude | author-link = Claude Berge
 | journal = [[Comptes rendus de l'Académie des Sciences|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}}</ref>

<ref name=berkramal>{{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]]
 | mr = 3230913
 | pages = 639–642
 | title = Estimating the number of connected components in sublinear time
 | volume = 114
 | year = 2014}}</ref>

<ref name=bollobas>{{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
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108192625/https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA6
 | url-status = live
 }}</ref>

<ref name=boost>{{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}}</ref>

<ref name=chvatal>{{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 (journal)|Discrete Mathematics]]
 | mr = 0316301
 | pages = 215–228
 | title = Tough graphs and Hamiltonian circuits
 | volume = 5
 | year = 1973}}</ref>

<ref name=cioaba>{{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| isbn = 978-0-8176-4788-9
 }}; see [https://books.google.com/books?id=0ymYdW1rtBUC&pg=PA361 proof of Lemma 5, p. 361] {{Webarchive|url=https://web.archive.org/web/20220108230453/https://books.google.com/books?id=0ymYdW1rtBUC&pg=PA361 |date=2022-01-08 }}</ref>

<ref name=cohav>{{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
 | access-date = 2022-01-10
 | archive-date = 2022-01-10
 | archive-url = https://web.archive.org/web/20220110174730/https://books.google.com/books?id=1ECLiFrKulIC&pg=PA97
 | url-status = live
 }}</ref>

<ref name=dst>{{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]]
 | mr = 1160258
 | pages = 253–280
 | title = A general approach to connected-component labeling for arbitrary image representations
 | volume = 39
 | year = 1992| s2cid = 1869184
 | citeseerx = 10.1.1.73.8846
 }}</ref>

<ref name=foldes>{{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
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107080529/https://books.google.com/books?id=A59RivXPMzkC&pg=PA199
 | url-status = live
 }}</ref>

<ref name=frikar>{{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}}</ref>

<ref name=subcritical>{{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</ref>

<ref name=supercritical>{{harvtxt|Frieze|Karoński|2016}}, 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39</ref>

<ref name=critical>{{harvtxt|Frieze|Karoński|2016}}, 2.3 Phase transition, pp. 39–45</ref>

<ref name=random-connectivity>{{harvtxt|Frieze|Karoński|2016}}, 4.1 Connectivity, pp. 64–68</ref>

<ref name=hhkp>{{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 <math>O\bigl(\log n(\log\log n)^2\bigr)</math> 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| s2cid = 15585534
 }}</ref>

<ref name=hoptar>{{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]]
 | pages = 372–378
 | title = Algorithm 447: efficient algorithms for graph manipulation
 | volume = 16| s2cid = 14772567 | doi-access = free
 }}</ref>

<ref name=jnp>{{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
 | access-date = January 8, 2022
 | archive-date = January 16, 2016
 | archive-url = https://web.archive.org/web/20160116090036/https://code.google.com/p/graphbook/
 | url-status = live
 }}</ref>

<ref name=knuth>{{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
 | access-date = March 1, 2022
 | archive-date = January 18, 2022
 | archive-url = https://web.archive.org/web/20220118183018/https://cs.stanford.edu/~knuth/fasc12a+.pdf
 | url-status = live
 }}</ref>

<ref name=kozen>{{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
 | s2cid = 27747202
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108192351/https://books.google.com/books?id=HFn1BwAAQBAJ&pg=PA20
 | url-status = live
 }}</ref>

<ref name=lewpap>{{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 (journal)|Theoretical Computer Science]]
 | mr = 666539
 | pages = 161–187
 | title = Symmetric space-bounded computation
 | volume = 19
 | year = 1982| doi-access = free
 }}</ref>

<ref name=lewzax>{{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
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108191703/https://books.google.com/books?id=fAZ-DwAAQBAJ&pg=PA145
 | url-status = live
 }}</ref>

<ref name=mcnosh>{{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| doi-access = 
 }}</ref>

<ref name=read>{{citation
 | last = Read | first = Ronald C. | author-link = Ronald C. Read
 | doi = 10.1016/S0021-9800(68)80087-0
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 224505
 | pages = 52–71
 | title = An introduction to chromatic polynomials
 | volume = 4
 | year = 1968| doi-access = free
 }}; see Theorem 2, p. 59, and corollary, p. 65</ref>

<ref name=reingold>{{citation
 | last = Reingold | first = Omer | author-link = Omer Reingold
 | doi = 10.1145/1391289.1391291 | doi-access = 
 | issue = 4
 | journal = [[Journal of the ACM]]
 | mr = 2445014
 | page = A17:1–A17:24
 | title = Undirected connectivity in log-space
 | volume = 55
 | year = 2008| s2cid = 207168478 }}</ref>

<ref name=skiena>{{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
 | bibcode = 2008adm..book.....S
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107183740/https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA196
 | url-status = live
 }}</ref>

<ref name=thuswa>{{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
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107215533/https://books.google.com/books?id=rFH7eQffQNkC&pg=PA9
 | url-status = live
 }}</ref>

<ref name=tutte-betti>{{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
 | access-date = 2022-01-07
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107081347/https://books.google.com/books?id=uTGhooU37h4C&pg=PA15
 | url-status = live
 }}</ref>

<ref name=tutte-matching>{{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| issue = 2 }}</ref>

<ref name=wilson>{{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| issue = 5 }}</ref>

<ref name=wood>{{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
 | isbn = 978-3-642-27848-8
 | access-date = 2022-01-08
 | archive-date = 2022-01-08
 | archive-url = https://web.archive.org/web/20220108225308/https://users.monash.edu/~davidwo/papers/EncPaper.pdf
 | url-status = live
 }}</ref>

<ref name=wulff-nilsen>{{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| isbn = 978-1-61197-251-1
 | s2cid = 13397958
 }}</ref>

}}

==External links==
*[http://www.mathworks.com/matlabcentral/fileexchange/42040-find-network-components MATLAB code to find components in undirected graphs], MATLAB File Exchange.
*[http://www.cs.sunysb.edu/~algorith/files/dfs-bfs.shtml Connected components], Steven Skiena, The Stony Brook Algorithm Repository

[[Category:Graph connectivity]]
[[Category:Graph theory objects]]