Representing relations using digraphs

6.3

A directed graph, or digraph, consists of a set V of vertices (or

nodes) together with a set E of ordered pairs of elements of V called

edges (or arcs).

a b

c d

The vertex a is called the initial vertex of the edge (a,b), and the

vertex b is called the terminal vertex of this edge.

An edge of the form (a,a) is called a loop.

The above digraph represents the relation E={(a,a), (a,c), (a,d), (c,a)}

on the set V={a,b,c,d}.

What can we say about the digraph representing a 1) reflexive,

2) symmetric, 3) antisymmetric, 4) transitive relation?

Previous slide

Back to first slide

View graphic version