A **directed graph**, or "**digraph**", is a graph whose
edges have direction and are called **arcs**. Arrows on the arcs
are used to encode the directional
information: an arc from vertex A to vertex B indicates that one may move from
A to B but not from B to A.

Suppose that you wished to go to the main branch of the Cincinnati Public Library. The following directed graph is a map to the library from the nearby major interstates:

We have obviously omitted a number of downtown streets for reasons of clarity. Similarly, we have labeled the arcs instead of the vertices in many cases; we trust it is obvious that the vertex connecting, for instance, 9th Street with Vine Street, is the intersection of 9th and Vine. Note that all of the streets in this directed graph are one-way; a two-way street would have arcs in both directions connecting vertices corresponding to neighboring intersections.

In a directed graph, vertices have both "**indegrees**" and "**outdegrees**": the indegree of a vertex
is the number of arcs leading to that vertex, and the outdegree of a vertex is the number of arcs leading away
from that vertex. In the directed graph above,

A vertex with an indegree of 0 is called a

- 9th & Walnut and I-75 N have an indegree of 0,
- I-75 and I-71 have an indegree of 1,
- and the remaining vertices have an indegree of 2;

- 5th and Walnut has an outdegree of 0,
- 9th & Vine, I-71, 8th & Vine and I-75 N have an outdegree of 1,
- and the remaining vertices have an outdegree of 2.

a directed graph with no cycles has at least one source and one sink.

Mis the element of the matrix M which is located at the intersection of the ith row and the jth column. The following matrix,_{i,j}

I-75 | I-71 | 9th & Vine | 9th & Walnut | 8th & Vine | 8th & Walnut | 7th & Vine | 7th & Walnut | 5th & Vine | 5th & Walnut | I-75 N | |
---|---|---|---|---|---|---|---|---|---|---|---|

I-75 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |

I-71 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

9th & Vine | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

9th & Walnut | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

8th & Vine | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

8th & Walnut | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |

7th & Vine | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |

7th & Walnut | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

5th & Vine | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |

5th & Walnut | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

I-75 N | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |

There are several things to notice about this matrix:

Our notion of connectivity changes somewhat when we talk about directed graphs:

- if the column corresponding to a vertex contains all 0s, the vertex is a source;
- if a row corresponding to a vertex contains all 0s, the vertex is a sink;
- the elements on the diagonal (M
_{i,i}) are all 0 if there are no loops in the graph;- and finally, most of the elements in a directed graph matrix are 0, and most of the nonzero elements are 1.

In the directed graph example above,

- a
walkthrough a directed graph is a sequence of vertices connected by arcs corresponding to the order of the vertices in the sequence;- a "
semi-walk" through a directed graph is a sequence of vertices in which the arc directions are ignored;- a
pathis still a walk with no repeated vertices, and a- "
semi-path" is a semi-walk with no repeated vertices.

I-75, 7th & Vine, 8th & Vine, 9th & Vine, I-75is a walk,

I-75, 7th & Vine, 5th & Vine, I-75is a semi-walk,

I-75, 7th & Vine, 8th & Vineis a path and

I-75, 7th & Vine, 5th & Vine, 5th & Walnut, 7 & Walnutis a semi-path. There are obviously many more examples of each: find them!

Using these definitions, we can further define various levels of connectivity:

Our directed graph example is strictly weakly connected, as is any directed graph with sources or sinks.

- a directed graph is connected (or "
unilaterally connected") if there is a path between any two vertices;- it is "
weakly connected" if there is a semi-path between any two vertices;- it is "
strongly connected" if there is a path in both directions between any two vertices;- it is strictly weakly connected if it is not unilaterally connected, and it is
- strictly unilaterally connected if it is not strongly connected.

A matrix is a special case of aWe now move to one of the most interesting applications of the directed graph: the finite state machine.data structurecalled anarray. Arrays can have any number of indices; that number is called thedimensionof the array. A matrix is a 2-dimensional array; a 1-dimensional array is sometimes called avector.When most of the elements in an array are zero, the nonzero elements are sometimes stored as a

sparse array. This is typically implemented using a different data structure called alinked list: each element in the list contains the values of the indices, the value of the array element, and a pointer to the next element in the list. Sometimes these lists are organized as one or more trees, and sometimes the lists are doubly linked, so they can be traversed in both directions. Trees are often implemented as doubly linked lists.Matrices are usually only stored as sparse arrays when there are a

lotof elements. Our 11 by 11 matrix above is too small to warrant storage as a sparse array. Only when there are hundreds of thousands or more elements, most of which are zero, would a sparse array typically be used. These occur most often in scientific applications.

Go to: Title Page Table of Contents Index

©2012, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.