Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders242

9.4 Path Relations

A basic question about a digraph is whether there is a path from one particular

vertex to another. So for any digraph,G, we are interested in a binary relation,G,

called thepath relationonV.G/where

u GvWWDthere is a path inGfromutov: (9.6)

Similarly, there is apositive path relation

a GCbWWDthere is a positive length path inGfromutov: (9.7)

Since merging a path fromutovwith a path fromvtowgives a walk, and

therefore a path by Theorem 9.2.3, fromutow, both path relations have a relational

property calledtransitivity:

Definition 9.4.1.A binary relation,R, on a set,A, istransitiveiff

.a R bANDb R c/ IMPLIES a R c

for everya;b;c 2 A.

Since there is a length-0 path from any vertex to itself, the path relation has

another relational property calledreflexivity:

Definition 9.4.2. A binary relation,R, on a set,A, isreflexiveiffa R afor all

a 2 A.

9.4.1 Composition of Relations

There is a simple way to extend composition of functions to composition of rela-

tions, and this gives another way to talk about walks and paths in digraphs.

Definition 9.4.3.LetRWB!C andSWA!Bbe binary relations. Then the

composition ofRwithSis the binary relation.RıS/WA!Cdefined by the

rule

a .RıS/ cWWD 9b 2 B:.a S b/AND.b R c/: (9.8)

This agrees with the Definition 4.3.1 of composition in the special case whenR

andSare functions.^2

(^2) The reversal of the order ofRandSin (9.8) is not a typo. This is so that relational composition
generalizes function composition. The value of functionfcomposed with functiongat an argument,
x, isf.g.x//. So in the composition,fıg, the functiongis applied first.