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.
Read more about this topic: Connected Component (graph Theory)
Famous quotes containing the word relation:
“The adolescent does not develop her identity and individuality by moving outside her family. She is not triggered by some magic unconscious dynamic whereby she rejects her family in favour of her peers or of a larger society.... She continues to develop in relation to her parents. Her mother continues to have more influence over her than either her father or her friends.”
—Terri Apter (20th century)