Component (graph theory)
In
The number of components in a given graph is an important
The components of a graph can be constructed in
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 of a graph belongs to one of the graph's components, which may be found as the induced subgraph of the set of vertices reachable from .[1] Every graph is the disjoint union of its components.[2] Additional examples include the following special cases:
- In an isolated vertex in any graph.[4]
- In a connected graph, there is exactly one component: the whole graph.[4]
- In a
- In a maximal clique. These graphs may be produced as the transitive closures of arbitrary undirected graphs, for which finding the transitive closure is an equivalent formulation of identifying the connected components.[6]
Another definition of components involves the equivalence classes of an equivalence relation defined on the graph's vertices. In an undirected graph, a vertex is reachable from a vertex if there is a path from to , or equivalently a
- It is reflexive: There is a trivial path of length zero from any vertex to itself.
- It is symmetric: If there is a path from to , the same edges in the reverse order form a path from to .
- It is transitive: If there is a path from to and a path from to , the two paths may be concatenated together to form a walk from to .
The equivalence classes 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 subgraphs formed by each of these equivalence classes.[7] Alternatively, some sources define components as the sets of vertices rather than as the subgraphs they induce.[8]
Similar definitions involving equivalence classes have been used to defined components for other forms of graph connectivity, including the weak components[9] and strongly connected components of directed graphs[10] and the biconnected components of undirected graphs.[11]
Number of components
The number of components of a given finite graph can be used to count the number of edges in its
A graph can be interpreted as a
The number of components arises in other ways in graph theory as well. In
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 vertex will find the entire component containing (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. Hopcroft & Tarjan (1973) describe essentially this algorithm, and state that it was already "well known".[19]
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 pixels 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, 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 patterns.[20]
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 time per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and is a very slowly growing inverse of the very quickly growing Ackermann function.[21] One application of this sort of incremental connectivity algorithm is in Kruskal's algorithm for minimum spanning trees, 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.[22] When both edge insertions and edge deletions are allowed, dynamic connectivity algorithms can still maintain the same information, in amortized time per change and time per connectivity query,
Components of graphs have been used in computational complexity theory to study the power of Turing machines that have a working memory limited to a logarithmic 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. 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, was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space reductions.[25] It was finally proven in 2008 that this connectivity problem can be solved in logarithmic space, and therefore that SL = L.[26]
In a graph represented as an
In random graphs
In random graphs 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 version of the Erdős–Rényi–Gilbert model, a graph on vertices is generated by choosing randomly and independently for each pair of vertices whether to include an edge connecting that pair, with probability of including an edge and probability of leaving those two vertices without an edge connecting them.[28] The connectivity of this model depends on , and there are three different ranges of 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 of . The analysis depends on a parameter , a positive constant independent of that can be arbitrarily close to zero.
- Subcritical
- In this range of , 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.[29]
- Critical
- 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 .[30]
- Supercritical
- There is a single giant component containing a linear number of vertices. For large values of its size approaches the whole graph: where is the positive solution to the equation . The remaining components are small, with logarithmic size.[31]
In the same model of random graphs, there will exist multiple connected components with high probability for values of 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 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.[32]
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.[33]
References
- ISBN 9788170234630, archivedfrom the original on 2022-01-08, retrieved 2022-01-07
- ^ Joyner, David; Nguyen, Minh Van; Phillips, David (May 10, 2013), "1.6.1 Union, intersection, and join", Algorithmic Graph Theory and Sage (0.8-r1991 ed.), Google, pp. 34–35, archived from the original on January 16, 2016, retrieved January 8, 2022
- ^ from the original on 2022-01-07, retrieved 2022-01-07
- ^ ISBN 978-1-118-03025-7, archivedfrom the original on 2022-01-07, retrieved 2022-01-07
- from the original on 2022-01-08, retrieved 2022-01-08
- MR 0856101
- ISBN 978-1-118-03143-8, archivedfrom the original on 2022-01-07, retrieved 2022-01-07
- ^ Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew (2001), "7.1 Connected components: Definitions", The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley, pp. 97–98
- ^ Knuth, Donald E. (January 15, 2022), "Weak components", The Art of Computer Programming, Volume 4, Pre-Fascicle 12A: Components and Traversal (PDF), pp. 11–14, archived (PDF) from the original on January 18, 2022, retrieved March 1, 2022
- ISBN 978-0-691-19061-7, archivedfrom the original on 2022-01-08, retrieved 2022-01-08
- from the original on 2022-01-08, retrieved 2022-01-08
- MR 0371694
- (PDF) from the original on 2022-01-08, retrieved 2022-01-08
- MR 0224505; see Theorem 2, p. 59, and corollary, p. 65
- MR 0023048
- MR 0100850
- MR 0316301
- S2CID 14772567
- S2CID 1869184
- ProQuest 303248045
- ISBN 978-1-84800-069-8, archivedfrom the original on 2022-01-07, retrieved 2022-01-07
- S2CID 13397958
- ^ Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Fully dynamic connectivity in amortized expected time", in Klein, Philip N. (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 510–520, S2CID 15585534
- MR 0666539
- S2CID 207168478
- MR 3230913
- MR 3675279
- ^ 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
- ^ Frieze & Karoński (2016), 2.3 Phase transition, pp. 39–45
- ^ Frieze & Karoński (2016), 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39
- ^ Frieze & Karoński (2016), 4.1 Connectivity, pp. 64–68
- ISBN 978-1-139-48927-0, archivedfrom the original on 2022-01-10, retrieved 2022-01-10
External links
- MATLAB code to find components in undirected graphs, MATLAB File Exchange.
- Connected components, Steven Skiena, The Stony Brook Algorithm Repository