<< Chapter < Page | Chapter >> Page > |
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>} .
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),
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?