0.6 Discrete structures relation  (Page 4/13)

For example Figure 1 is a digraph with 3 vertices and 4 arcs.

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 digraph in Figure 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 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. x0 is the initial vertex and xn is the terminal vertex of the path.

A path is called a directed path   if  <xi, xi + 1>∈A ,   for every i,   0 ≤i ≤n -1.

If the initial and the terminal vertices of a path are the same, that is,   x0 = xn,   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 G3 given in Figure 3,

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),