Connected Component (graph Theory) - An Equivalence Relation

An Equivalence Relation

An alternative way to define connected components involves the equivalence classes of an equivalence relation that is defined on the vertices of the graph. In an undirected graph, a vertex v is reachable from a vertex u if there is a path from u to v. In this definition, a single vertex is counted as a path of length zero, and the same vertex may occur more than once within a path. 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: If there is a path from u to v, the same edges form a path from v to u.
• It is transitive: If there is a path from u to v and a path from v to w, the two paths may be concatenated together to form a path from u to w.

The connected components are then the induced subgraphs formed by the equivalence classes of this relation.