48 l;\ Theory of Computer Science
Fig. 2.4 A directed graph.
DefInitions (i) If (Vi, Vi) is associated with an edge e, then Vi and Vj are called
the end vertices of e; Vi is called a predecessor of Vj which is a successor of Vi'
In Fig. 2.3. 1'~ and 1'3 are the end vertices of e3' In Fig. 2.4, v~ is a
predecessor of 1'3 which is a successor of V~. Also, 1'4 is a predecessor of v~ and
successor of 1'3'
(ii) If G is a digraph, the undirected graph corresponding to G is the
undirected graph obtained by considering the edges and vertices of G, but
ignoring the 'direction' of the edges. For example, the undirected graph
corresponding to the digraph given in Fig. 2.4 is shown in Fig. 2.5.
Fig. 2.5 A graph.
DefInition 2.13 The degree of a vertex in a graph (directed or undirected) is
the number of edges with V as an end vertex. (A self-loop is counted twice while
calculating the degree.) In Fig. 2.3, deg(1']) = 2, deg(1'3) =3, deg(1'2) = 5. In
Fig. 2.4, deg(1'~) = 3, deg(1'4) = 2.
We now mention the following theorem without proof.
Theorem 2.4 The number of vertices of odd degree in any graph (directed or
undirected) is even.
DefInition 2.14 A path in a graph (undirected or directed) is an alternating
sequence of vertices and edges of the form v]e]1'~e~ ... vn_len_]VI1' beginning
and ending with vertices such that ei has Vi and Vi+] as its end vertices and
no edge or vertex is repeated in the sequence. The path is said to be a path
from 1'1 to VIZ"
For example. 1'je~1'3e3v2 is a path in Fig. 2.3. It is a path from V] to 1'2' In
Fig. 2.4. Vje2V3e3v2 is a path from v] to 1'2' vlej1'2 is also a path from Vj to 1'2'
Fig. 2.4 A directed graph.
DefInitions (i) If (Vi, Vi) is associated with an edge e, then Vi and Vj are called
the end vertices of e; Vi is called a predecessor of Vj which is a successor of Vi'
In Fig. 2.3. 1'~ and 1'3 are the end vertices of e3' In Fig. 2.4, v~ is a
predecessor of 1'3 which is a successor of V~. Also, 1'4 is a predecessor of v~ and
successor of 1'3'
(ii) If G is a digraph, the undirected graph corresponding to G is the
undirected graph obtained by considering the edges and vertices of G, but
ignoring the 'direction' of the edges. For example, the undirected graph
corresponding to the digraph given in Fig. 2.4 is shown in Fig. 2.5.
Fig. 2.5 A graph.
DefInition 2.13 The degree of a vertex in a graph (directed or undirected) is
the number of edges with V as an end vertex. (A self-loop is counted twice while
calculating the degree.) In Fig. 2.3, deg(1']) = 2, deg(1'3) =3, deg(1'2) = 5. In
Fig. 2.4, deg(1'~) = 3, deg(1'4) = 2.
We now mention the following theorem without proof.
Theorem 2.4 The number of vertices of odd degree in any graph (directed or
undirected) is even.
DefInition 2.14 A path in a graph (undirected or directed) is an alternating
sequence of vertices and edges of the form v]e]1'~e~ ... vn_len_]VI1' beginning
and ending with vertices such that ei has Vi and Vi+] as its end vertices and
no edge or vertex is repeated in the sequence. The path is said to be a path
from 1'1 to VIZ"
For example. 1'je~1'3e3v2 is a path in Fig. 2.3. It is a path from V] to 1'2' In
Fig. 2.4. Vje2V3e3v2 is a path from v] to 1'2' vlej1'2 is also a path from Vj to 1'2'