SKEDSOFT

HAND SHAKING DILEMMA: In a digraph D, the sum of the out-degree of all vertices is equal to the sum of the in-degrees of all vertices, each sum being equal to the numbe of edges in D.
For example, the digraph in Fig. 8.1, we note that the digraphs has 6 vertices and 9 edges and that the sums of the out-degrees and in-degrees of its vertices are

DIRECTED WALK, DIRECTED PATH, DIRECTED CIRCUIT

Directed walk: A directed walk or a directed trail in D is a finite sequence whose terms are alternately vertices and edges in D such that each edge is incident out of the vertex preceeding it in the sequence and incident into the vertex following it.

A directed walk or a directed trail in D is a sequence of the form v0 e1 v1 e2 ..... ek vk where v0, v1, ...... vk are vertices of D in some order and e1, e2, ..... ek are edges of D such that the edge ei has vi – 1 as the initial vertex and vi as the terminal vertex, i = 1, 2, ..... k.

A vertex can appear more than once in a directed walk but not an edge.

The vertex with which a directed walk begins is called its initial vertex and the vertex with which its ends is called its final or terminal vertex.

Directed path
An open directed walk in which no vertex is repeated is called a directed path.

Directed circuit
A closed directed walk in which no vertices, except the initial and final vertices are repeated is called a directed circuit or a directed cycle.

Length
The number of edges present in a directed walk, directed path, directed circuit is called its length.

For example, in the digraph shown in Fig. (8.1)
(i) v1e1v2e2v3e3v3 is an open directed walk which is not a directed path, its length is 3.
(ii) v6e6v1e1v2e2v3 is an open directed walk which is a directed path, its length is 3.
(iii) v1e1v2e9v1 or v1v2v1 is a closed directed walk which is a directed circuit, its length is 2.