Editing Component (graph theory) (section)

==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}}