Chapter 9 Directed graphs & Partial Orders258
ReflexivityRisreflexivewhen
8 x 2 A: x R x:Every vertex inRhas a self-loop.Irreflexivity Risirreflexivewhen
NOTŒ 9 x 2 A: x R xç:There are no self-loops inR.Symmetry Rissymmetricwhen
8 x;y 2 A: x R yIMPLIESy R x:If there is an edge fromxtoyinR, then there is an edge back fromytox
as well.AsymmetryRisasymmetricwhen
8 x;y 2 A: x R yIMPLIES NOT.y R x/:There is at most one directed edge between any two vertices inR, and there
are no self-loops.Antisymmetry Risantisymmetricwhen
8 x¤y 2 A: x R yIMPLIES NOT.y R x/:Equivalently,8 x;y 2 A: .x R yANDy R x/IMPLIES xDy:There is at most one directed edge between any two distinct vertices, but
there may be self-loops.Transitivity Ristransitiveif
8 x;y;z 2 A: .x R yANDy R z/IMPLIESx R z:If there is a positive length path fromutov, then there is an edge fromu
tov.