Data Structures and Algorithms with Object-Oriented Design Patterns in C++

### Terminology

Consider a directed graph as given by Definition .

• Each element of is called a vertex  or a node  of G. Hence, is the set of vertices (or nodes) of G.
• Each element of is called an edge  or an arc of G. Hence, is the set of edges (or arcs) of G.
• An edge can be represented as . An arrow that points from v to w is known as a directed arc  . Vertex w is called the head of the arc because it is found at the arrow head. Conversely, v is called the tail of the arc. Finally, vertex w is said to be adjacent  to vertex v.
• An edge e=(v,w) is said to emanate   from vertex v. We use notation to denote the set of edges emanating from vertex v. I.e.,
• The out-degree   of a node is the number of edges emanating from that node. Therefore, the out-degree of v is
• An edge e=(v,w) is said to be incident   on vertex w. We use notation to denote the set of edges incident on vertex w. I.e.,
• The in-degree   of a node is the number of edges incident on that node. Therefore, the in-degree of w is

For example, Table  enumerates the sets of emanating and incident edges and the in- and out-degrees for each of the vertices in graph shown in Figure .

 vertex v out-degree in-degree a 2 1 b 1 1 c 2 2 d 1 2

There is still more terminology to be introduced, but in order to do that, we need the following definition:

Definition (Path and Path Length)

A path  in a directed graph is a non-empty sequence of vertices

where for such that for . The length of path P is k-1.

For example, consider again the graph shown in Figure . Among the paths contained in there is the path of length zero, ; the path of length one, ; the path of length two, ; and so on. In fact, this graph generates an infinite number of paths! (To see how this is possible, consider that is a path in ). Notice too the subtle distinction between a path of length zero, say , and the path of length one .