Determine whether the relations represented by the following

Determine whether the relations represented by the following directed graphs are reflexive, irreflexive, symmetric, antisymmetric, asymmetric, and/or transitive.

Solution

If every node has a loop, a relation is reflexive.

If every node does not have a loop, a relation is irreflexive.

If, for every edge, there is an edge in the other direction, then the relation is symmetric. (Loops are allowed, and do not need edges in the “other” direction)

If, for every edge, there is not an edge in the other direction, then the relation is asymmetric. (Loops are not allowed in an asymmetric digraph)

If, for every edge, there is not an edge in the other direction, then the relation is antisymmetric. (Loops are allowed in the digraph)

A digraph is transitive if, for there is an edge from a to c when there is a edge from a to b and from b to c.