On the set of nonnegative integers, we can define a relation
if and only if
Then 2 ≡ 5, 12 ≡ 0, and 0 ≡ 36. Clearly this is an equivalence relation, as it
satisfies reflexivity, symmetry, and transitivity.
If S is a set on which we have a defined equivalence relation, then we can
use this equivalence to partition the set into equivalence classes. Each
equivalence class contains all and only equivalent elements.
Graphs and Trees
A graph is a construct consisting of two finite sets, the set V = {υ 1 , υ 2 ,…, υ n } of
vertices and the set E = {e 1 , e 2 ,…, e m } of edges. Each edge is a pair of vertices
from V, for instance,
is an edge from υ j to υ k . We say that the edge e i is an outgoing edge for υ j and an
incoming edge for υ k . Such a construct is actually a directed graph (digraph),
since we associate a direction (from υ j to υ k ) with each edge. Graphs may be
labeled, a label being a name or other information associated with parts of the
graph. Both vertices and edges may be labeled.
Graphs are conveniently visualized by diagrams in which the vertices are
represented as circles and the edges as lines with arrows connecting the vertices.
The graph with vertices {υ 1 , υ 2 , υ 3 } and edges {(υ 1 , υ 3 ), (υ 3 , υ 1 ), (υ 3 , υ 2 ), (υ 3 , υ 3 )}
is depicted in Figure 1.1.
A sequence of edges (υ i , υ j ), (υ j , υ k ),…, (υ m , υ n ) is said to be a walk from υ i to
υ n . The length of a walk is the total number of edges traversed in going from the
initial vertex to the final one. A walk in which no edge is repeated is said to be a
path; a path is simple if no vertex is repeated. A walk from υ i to itself with no