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:
“Skepticism is unbelief in cause and effect. A man does not see, that, as he eats, so he thinks: as he deals, so he is, and so he appears; he does not see that his son is the son of his thoughts and of his actions; that fortunes are not exceptions but fruits; that relation and connection are not somewhere and sometimes, but everywhere and always; no miscellany, no exemption, no anomaly,—but method, and an even web; and what comes out, that was put in.”
—Ralph Waldo Emerson (1803–1882)