Page 615 - Discrete Mathematics and Its Applications

594 9 / Relations

The matrix representing the composite of two relations can be used to find the matrix
for M R . In particular,
n
[n]
M R = M ,
n
R
from the definition of Boolean powers. Exercise 35 asks for a proof of this formula.

2
EXAMPLE 6 Find the matrix representing the relation R , where the matrix representing R is
⎡ ⎤
0 1 0
M R = ⎣ 0 1 1 ⎦ .
1 0 0

2
Solution: The matrix for R is
⎡ ⎤
0 1 1
M 2 = M [2] = ⎣ 1 1 1 ⎦ .
R
R
0 1 0
▲

Representing Relations Using Digraphs

We have shown that a relation can be represented by listing all of its ordered pairs or by
using a zero–one matrix. There is another important way of representing a relation using a
pictorial representation. Each element of the set is represented by a point, and each ordered
pair is represented using an arc with its direction indicated by an arrow. We use such pictorial
representations when we think of relations on a finite set as directed graphs,or digraphs.

DEFINITION 1 A directed graph,or digraph, consists of a set V of vertices (or nodes) together with a set
E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial
vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge.

An edge of the form (a, a) is represented using an arc from the vertex a back to itself. Such
an edge is called a loop.

EXAMPLE 7 The directed graph with vertices a, b, c, and d, and edges (a, b), (a, d), (b, b), (b, d), (c, a),
(c, b), and (d, b) is displayed in Figure 3. ▲

a b
The relation R on a set A is represented by the directed graph that has the elements of A as its
vertices and the ordered pairs (a, b), where (a, b) ∈ R, as edges. This assignment sets up a one-
to-one correspondence between the relations on a set A and the directed graphs with A as their
set of vertices. Thus, every statement about relations corresponds to a statement about directed
graphs, and vice versa. Directed graphs give a visual display of information about relations. As
such, they are often used to study relations and their properties. (Note that relations from a set
d c A to a set B can be represented by a directed graph where there is a vertex for each element of
A and a vertex for each element of B, as shown in Section 9.1. However, when A = B, such
FIGURE 3 representation provides much less insight than the digraph representations described here.) The
A Directed Graph. use of directed graphs to represent relations on a set is illustrated in Examples 8–10.