Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
555
Directed Graphs and Binary Relations
Suppose G is a directed graph with n nodes and no parallel arcs. Let N be the set
of nodes. If (n i , n j ) is an ordered pair of nodes, then there either is or is not an arc
in G from n i to n j . We can use this property to define a binary relation on the set N:
n i r n j 4 there is an arc in G from n i to n j
This relation is the adjacency relation of the graph.
example 1
For the directed graph of Figure 7.1, the adjacency relation is 5(1, 2), (1, 3), (3,3),
(4, 1), (4, 2), (4,3)6.
2
4
1
3
Figure 7.1
Conversely, if r is a binary relation on a set N, we can define a directed graph G
with N as the set of nodes, and an arc from n i to n j if and only if n i r n j . G will have
no parallel arcs.
example 2
For the set N = 51, 2, 3, 46 and the binary relation 5(1, 4), (2, 3), (2, 4), (4, 1)6 on
N, we obtain the associated directed graph shown in Figure 7.2.
4
1
3
2
Figure 7.2
We now have another one-to-one correspondence:
Binary
relations on
n-element sets
Directed graphs
with n nodes,
no parallel arcs
(2)