1.2 Directed Graph

If the edges of GG are ordered pairs, then GG is a directed graph. In a directed graph, v,ww,v(v,w)\neq(w,v).

A directed graph is often referred to as a digraph. If edge ee of a digraph is represented by v,w(v,w), then ee is an edge from vv to ww. Vertex ww is adjacent to vertex vv. Vertex vv is not adjacent to vertex ww unless the edge w,v(w,v) also exists in GG. The number of vertices adjacent to vertex vv is the degree of vv. In-degree indicates the number of edges incident upon vv. Out-degree indicates the number of edges emanating from vv.

Figure 1 depicts a directed graph with six vertices and ten edges. In the figure, the arrowheads indicate the direction of the edge.

Figure 1: Example of a Directed Graph

Table 1 summarizes the degree of each vertex in Figure 1.

Table 1: Vertex Degree Summary for Figure 1
Vertex Degree In-Degree Out-Degree
1 2 1 1
2 4 1 3
3 4 2 2
4 4 3 1
5 3 2 1
6 3 1 2