In Chapter 5 we represented partial orderings on a set by using a Hasse
diagram. How does this representation differ from the directed graph representation? The Hasse diagram is a simplification of the directed graph representation.
Suppose that G is the directed graph representation of a partial ordering. Because
a partial ordering is reflexive, G will have a loop at each node. We can eliminate
these loops in the Hasse diagram without losing any information because we
know that each node has a loop; that is, each node is related to itself. Because a
partial ordering is transitive, if a r b and b r c, then a r c. In the directed graph
there would be an arc from a to b, an arc from b to c, and an arc from a to c. In
the Hasse diagram we can eliminate the arc from a to c without losing any information if we keep the transitive property in mind. Finally, the Hasse diagram
is not a directed graph at all, but we did impose the convention that if a is an
immediate predecessor of b, then node a will appear below node b in the Hasse
diagram. Thus we could achieve a directed graph from the Hasse diagram by
making all the arc directions point upward. The antisymmetry property prevents
any potential conflict where node a should be below node b and node b should be
below node a.
In Chapter 5 we also noted set operations that could be performed on two
binary relations r and s on a set N, r c s and r d s. The relation r c s is the
union of the ordered pairs in r or s, while r d s is the intersection of the ordered
pairs in r and s. Let r and s be the Boolean matrices for r and s, respectively.
The Boolean matrix for r c s will have a 1 in position i, j if and only if there is a
1 in position i, j of r or a 1 in position i, j of s. Each entry in the Boolean matrix
for r c s is thus the maximum of the two corresponding entries in r and s, so
the Boolean matrix for r c s is r ~ s (see the discussion of Boolean matrix operations in Section 5.7). Similarly, the Boolean matrix for r d s will have a 1 in
position i, j if and only if there is a 1 in position i, j of both r and s. Therefore the
Boolean matrix for r d s is r ` s.
Reachability
The “reachability” property has an interesting interpretation in each of the three
equivalent forms in (3)—directed graph, adjacency relation, and adjacency matrix. We already have a definition for this term for directed graphs from Section 6.1,
which we’ll restate now.
Definition ReAchABle NoDe
In a directed graph, node n j is reachable from node n i if there is a path from n i
to n j .
In a system modeled by a directed graph (a data flow diagram, for example)
with a “start node,” any node that is unreachable from the start node can never affect the system and thus can be eliminated. If the directed graph represents something like airline routes or communication paths in a computer network, it would
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
557
example 4
In the directed graph of Figure 7.2, node 3 is not reachable from node 4 or node 1.
Node 1 is reachable from node 2 by the path 2–4–1.
diagram. How does this representation differ from the directed graph representation? The Hasse diagram is a simplification of the directed graph representation.
Suppose that G is the directed graph representation of a partial ordering. Because
a partial ordering is reflexive, G will have a loop at each node. We can eliminate
these loops in the Hasse diagram without losing any information because we
know that each node has a loop; that is, each node is related to itself. Because a
partial ordering is transitive, if a r b and b r c, then a r c. In the directed graph
there would be an arc from a to b, an arc from b to c, and an arc from a to c. In
the Hasse diagram we can eliminate the arc from a to c without losing any information if we keep the transitive property in mind. Finally, the Hasse diagram
is not a directed graph at all, but we did impose the convention that if a is an
immediate predecessor of b, then node a will appear below node b in the Hasse
diagram. Thus we could achieve a directed graph from the Hasse diagram by
making all the arc directions point upward. The antisymmetry property prevents
any potential conflict where node a should be below node b and node b should be
below node a.
In Chapter 5 we also noted set operations that could be performed on two
binary relations r and s on a set N, r c s and r d s. The relation r c s is the
union of the ordered pairs in r or s, while r d s is the intersection of the ordered
pairs in r and s. Let r and s be the Boolean matrices for r and s, respectively.
The Boolean matrix for r c s will have a 1 in position i, j if and only if there is a
1 in position i, j of r or a 1 in position i, j of s. Each entry in the Boolean matrix
for r c s is thus the maximum of the two corresponding entries in r and s, so
the Boolean matrix for r c s is r ~ s (see the discussion of Boolean matrix operations in Section 5.7). Similarly, the Boolean matrix for r d s will have a 1 in
position i, j if and only if there is a 1 in position i, j of both r and s. Therefore the
Boolean matrix for r d s is r ` s.
Reachability
The “reachability” property has an interesting interpretation in each of the three
equivalent forms in (3)—directed graph, adjacency relation, and adjacency matrix. We already have a definition for this term for directed graphs from Section 6.1,
which we’ll restate now.
Definition ReAchABle NoDe
In a directed graph, node n j is reachable from node n i if there is a path from n i
to n j .
In a system modeled by a directed graph (a data flow diagram, for example)
with a “start node,” any node that is unreachable from the start node can never affect the system and thus can be eliminated. If the directed graph represents something like airline routes or communication paths in a computer network, it would
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
557
example 4
In the directed graph of Figure 7.2, node 3 is not reachable from node 4 or node 1.
Node 1 is reachable from node 2 by the path 2–4–1.