1.2 Directed Graph

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

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

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