Relation

Digraph



Subjects to be Learned

Contents

A digraph is short for directed graph, and it is a diagram composed of points called vertices (nodes) and arrows called arcs going from a vertex to a vertex.
For example the figure below is a digraph with 3 vertices and 4 arcs.



                         G1

In this figure the vertices are labeled with numbers 1, 2, and 3.

Mathematically a digraph is defined as follows.
Definition (digraph): A digraph is an ordered pair of sets G = (V, A), where V is a set of vertices and A is a set of ordered pairs (called arcs) of vertices of V.

In the example, G1 , given above, V = { 1, 2, 3 } , and A = { <1, 1>, <1, 2>, <1, 3>, <2, 3> } .

Digraph representation of binary relations
A binary relation on a set can be represented by a digraph.
Let R be a binary relation on a set A, that is R is a subset of A A.
Then the digraph, call it G, representing R can be constructed as follows:
    1. The vertices of the digraph G are the elements of A, and
    2. <x, y> is an arc of G from vertex x to vertex y if and only if <x, y> is in R.

Example: The less than relation R on the set of integers A = {1, 2, 3, 4} is the set {<1, 2> , <1, 3>, <1, 4>, <2, 3> , <2, 4> , <3, 4> } and it can be represented by the following digraph.




                    G2

Let us now define some of the basic concepts on digraphs.

Definition (loop): An arc from a vertex to itself such as <1, 1>, is called a loop (or self-loop)
Definition (degree of vertex): The in-degree of a vertex is the number of arcs coming to the vertex, and the out-degree is the number of arcs going out of the vertex.
For example, the in-degree of vertex 2 in the digraph G2 shown above is 1, and the out-degree is 2.
Definition (path): A path from a vertex x0 to a vertex xn in a digraph G = (V, A) is a sequence of vertices x0 , x1 , ....., xn that satisfies the following:
for each i,  0 i n - 1 ,   <xi , xi + 1> A , or   <xi + 1 , xi> A ,   that is, between any pair of vertices there is an arc connecting them.
A path is called a directed path   if   <xi , xi + 1> A ,   for every i,   0 i n - 1 .
If no arcs appear more than once in a path, the path is called a simple path. A path is called elementary if no vertices appear more than once in it.

Note: There are two different definitions for "simple path". Here we follow the definition of Berge[1], Liu[2], Rosen[3] and others. A "simple path" according to another group (Cormen et al[4], Stanat and McAllister[5] and others) is a path in which no vertices appear more than once.

If the initial and the terminal vertices of a path are the same, that is,   x0 = xn ,   then the path is called a cycle .
Definition(connected graph): A digraph is said to be connected if there is a path between every pair of its vertices.

Example: In the digraph G3 given below,
     1, 2, 5 is a simple and elementary path but not directed,
     1, 2, 2, 5 is a simple path but neither directed nor elementary.
     1, 2, 4, 5 is a simple elementary directed path,
     1, 2, 4, 5, 2, 4, 5 is a directed path but not simple (hence not elementary),
     1, 3, 5, 2, 1 is a simple elementary cycle but not directed, and
     2, 4, 5, 2 is a simple elementary directed cycle.

This digraph is connected.














                              G3

Sometimes we need to refer to part of a given digraph. A partial digraph of a digraph is a digraph consisting of arbitrary numbers of vertices and arcs of the given digraph, while a subdigraph is a digraph consisting of an arbitrary number of vertices and all the arcs between them of the given digraph. Formally they are defined as follows:
Definition (subdigraph, partial digraph): Let G = ( V, A ) be a digraph. Then a digraph ( V', A' ) is a partial digraph of G ,  if   V' V ,  and  A' A ( V' V' ) .  It is a subdigraph of G ,  if   V' V ,  and  A'  =  A ( V' V' )

A partial digraph and a subdigraph of G3 given above are shown below.






















Test Your Understanding of Digraph

Indicate which of the following statements are correct and which are not.
Click True or False , then Submit. There are two sets of questions.


The digraph in the exercise questions below is G3 repeated below unless otherwise specified.

















Next -- Digraph Representaion of Binary Relation

Back to Schedule
Back to Table of Contents