Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Component (graph theory)
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a component of an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> is a <a href="/facts/Connected_graph/FSNjsYhz">connected</a> <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> that is not part of any larger connected subgraph. The components of any graph partition its vertices into <a href="/facts/Disjoint_set/nLr8XRVd">disjoint sets</a>, and are the <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraphs</a> of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. </p><p>The number of components in a given graph is an important <a href="/facts/Graph_invariant/bjuIvgb1">graph invariant</a>, and is closely related to invariants of <a href="/facts/Matroid/5bLcGlRF">matroids</a>, <a href="/facts/Topological_space/v2ut7CbK">topological spaces</a>, and <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a>. In <a href="/facts/Random_graph/gfQhq1Sz">random graphs</a>, a frequently occurring phenomenon is the incidence of a <a href="/facts/Giant_component/jIjS7zhM">giant component</a>, one component that is significantly larger than the others; and of a <a href="/facts/Percolation_threshold/z67jYyyF">percolation threshold</a>, an edge probability above which a giant component exists and below which it does not. </p><p>The components of a graph can be constructed in <a href="/facts/Linear_time/77T62gmf">linear time</a>, and a special case of the problem, <a href="/facts/Connected-component_labeling/DjFKJxx8">connected-component labeling</a>, is a basic technique in <a href="/facts/Image_analysis/woLB8cX7">image analysis</a>. <a href="/facts/Dynamic_connectivity/L0DX80bl">Dynamic connectivity</a> algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, connected components have been used to study algorithms with limited <a href="/facts/Space_complexity/nsnAW5cV">space complexity</a>, and <a href="/facts/Sublinear_time/77T62gmf">sublinear time</a> algorithms can accurately estimate the number of components. </p>