Relation

Digraph

### Subjects to be Learned

- digraph
- vertex
- arc
- loop
- in-degree, out-degree
- path,
directed path,
simple path
- cycle
- connected graph
- partial digraph
- subdigraph

### 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.

*G*_{1}

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, *G*_{1} , 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.

*G*_{2}

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 *G*_{2}
shown above
is *1*, and the out-degree is *2*.

**Definition (path):**
A **path** from a vertex *x*_{0}
to a vertex *x*_{n} in a digraph *G* = (*V, A*)
is a sequence of vertices
*x*_{0} , x_{1} , ....., x_{n}
that satisfies the following:

for each *i*, *0
i
n - 1
* ,
**<***x*_{i} , x_{i + 1}>
*A* ,
or
**<***x*_{i + 1} , x_{i}>
*A* ,
that is, between any pair of vertices there is an arc connecting them.

*x*_{0} is the **initial vertex** and *x*_{n}
is the **terminal vertex** of the path.

A path is called a **directed path** if
**<***x*_{i} , x_{i + 1}>
*A* ,
for every *i*, *0
i
n - 1
* .

If the initial and the terminal vertices of a path are the same, that is,
*x*_{0} = x_{n} ,
then the path
is called a **cycle** .

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 except for the initial and terminal vertices of a cycle. In a simple cycle one vertex appears twice in the sequence: once as the initial vertex
and once
as the terminal vertex.

**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.

**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 *G*_{3} 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.

*G*_{3}

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 *G*_{3} 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 ***G*_{3} repeated below unless otherwise specified.

**
Next -- Digraph Representaion of Binary Relation **

Back to Schedule

Back to Table of Contents