Page 616 - Discrete Mathematics and Its Applications

9.3 Representing Relations 595

EXAMPLE 8 The directed graph of the relation

R ={(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)}

on the set {1, 2, 3, 4} is shown in Figure 4. ▲

EXAMPLE 9 What are the ordered pairs in the relation R represented by the directed graph shown in Figure 5?

Solution: The ordered pairs (x, y) in the relation are

R ={(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3)}.

Each of these pairs corresponds to an edge of the directed graph, with (2, 2) and (3, 3) corre-
sponding to loops. ▲

The directed graph representing a relation can be used to determine whether the relation
We will study directed
graphs extensively in has various properties. For instance, a relation is reflexive if and only if there is a loop at every
Chapter 10. vertex of the directed graph, so that every ordered pair of the form (x, x) occurs in the relation.
A relation is symmetric if and only if for every edge between distinct vertices in its digraph
there is an edge in the opposite direction, so that (y, x) is in the relation whenever (x, y) is
in the relation. Similarly, a relation is antisymmetric if and only if there are never two edges
in opposite directions between distinct vertices. Finally, a relation is transitive if and only if
whenever there is an edge from a vertex x to a vertex y and an edge from a vertex y to a
vertex z, there is an edge from x to z (completing a triangle where each side is a directed edge
with the correct direction).

Remark: Note that a symmetric relation can be represented by an undirected graph, which is a
graph where edges do not have directions. We will study undirected graphs in Chapter 10.

EXAMPLE 10 Determine whether the relations for the directed graphs shown in Figure 6 are reflexive, sym-
metric, antisymmetric, and/or transitive.

Solution: Because there are loops at every vertex of the directed graph of R, it is reflexive. R is
neither symmetric nor antisymmetric because there is an edge from a to b but not one from b to
a, but there are edges in both directions connecting b and c. Finally, R is not transitive because
there is an edge from a to b and an edge from b to c, but no edge from a to c.

a b
a
1 2
1 2

b c c d
4 3 4 3 (a) Directed graph of R (b) Directed graph of S

FIGURE 4 The FIGURE 5 The FIGURE 6 The Directed Graphs of the
Directed Graph Directed Graph Relations R and S.
of the Relation R. of the Relation R.