Chapter 9 Directed graphs & Partial Orders350
Problem 9.10.
There is a simple and useful way to extend composition of functions to composition
of relations. Namely, letRWB! CandSWA!Bbe relations. Then the
composition ofRwithSis the binary relation.RıS/WA!Cdefined by the
rule
a .RıS/ cWWD 9b 2 B:.b R c/AND.a S b/:
This agrees with the Definition 4.3.1 of composition in the special case whenR
andSare functions.
We can represent a relation,S, between two setsAD fa 1 ;:::;angandBD
fb 1 ;:::;bmgas annmmatrix,MS, of zeroes and ones, with the elements ofMS
defined by the rule
MS.i;j/D 1 IFF aiS bj:
If we represent relations as matrices this way, then we can compute the compo-
sition of two relationsRandSby a “boolean” matrix multiplication, ̋, of their
matrices. Boolean matrix multiplication is the same as matrix multiplication except
that addition is replaced byOR, multiplication is replaced byAND, and 0 and 1 are
used as the Boolean valuesFalseandTrue. Namely, supposeRWB!Cis a bi-
nary relation withCDfc 1 ;:::;cpg. SoMRis anmpmatrix. ThenMS ̋MR
is annpmatrix defined by the rule:
ŒMS ̋MRç.i;j/WWDORmkD 1 ŒMS.i;k/ANDMR.k;j/ç: (9.13)Prove that the matrix representation,MRıS, ofRıSequalsMS ̋MR(note
the reversal ofRandS).
Problem 9.11.
Suppose that there arenchickens in a farmyard. Chickens are rather aggressive
birds that tend to establish dominance in relationships by pecking; hence the term
“pecking order.” In particular, for each pair of distinct chickens, either the first
pecks the second or the second pecks the first, but not both. We say that chickenu
virtually peckschickenvif either:
Chickenudirectly pecks chickenv, or Chickenupecks some other chickenwwho in turn pecks chickenv.A chicken that virtually pecks every other chicken is called aking chicken.
We can model this situation with achicken digraphwhose vertices are chickens
with an edge from chickenuto chickenvprecisely whenupecksv. In the graph