556
Graph Algorithms
Of course, a one-to-one correspondence means the existence of a bijection. If
function composition is carried out on the bijections in (1) and (2), the result is a
bijection that gives us a one-to-one correspondence between binary relations and
matrices. Thus we have three equivalent sets:
Binary
relations on
n-element sets
Directed graphs
with n nodes,
no parallel arcs
n × n Boolean
matrices
(3)
An item from any of the three sets has corresponding representations in the other
two sets.
praCtiCe 1 Give the collection of ordered pairs in the adjacency relation for the following Boolean
matrix; also draw the directed graph.
≥
0 0 0 0
1 1 0 0
1 0 0 1
0 0 0 0
¥
Recall the reflexive, symmetric, antisymmetric, and transitive properties of a
binary relation on a set that we studied in Chapter 5. If a binary relation on a set
N has a certain property, it will be reflected in the corresponding graph and the
corresponding Boolean matrix. Conversely, certain characteristics of a directed
graph or of a Boolean matrix imply certain properties of the corresponding adjacency relation.
example 3
If r is a reflexive relation on a set N, then for each n i [ N, n i r n i . In the corresponding directed graph there will be a loop at each node, and in the corresponding
Boolean matrix there will be 1s on the main diagonal.
praCtiCe 2 Explain why the corresponding binary relation is not antisymmetric for the directed
graph in Figure 6.13 reproduced here.
1
2
a 2
a 1
a 3
a 2
a 6
a 5
a 4
3
4
■
■