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:
“Much poetry seems to be aware of its situation in time and of its relation to the metronome, the clock, and the calendar. ... The season or month is there to be felt; the day is there to be seized. Poems beginning “When” are much more numerous than those beginning “Where” of “If.” As the meter is running, the recurrent message tapped out by the passing of measured time is mortality.”
—William Harmon (b. 1938)