Terminology

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

Table: Emanating and Incident Edge Sets for Graph in Figure

**Table:** Emanating and Incident Edge Sets for Graph 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 .