Directed Graphs

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 source (since one can only leave it) and a vertex with an outdegree of 0 is called a sink (since one cannot leave it). It is relatively easy to see that
a directed graph with no cycles has at least one source and one sink.

Matrices

Directed graphs are often described using matrices (singular matrix). For our purposes, a matrix is a table whose rows and columns are labeled, usually by numbers. The entries in the table are called matrix elements and are typically identified using subscripts:
Mi,j
is the element of the matrix M which is located at the intersection of the ith row and the jth column. The following matrix, in which each element Mi,j is the number of arcs from vertex i to vertex j, describes the directed graph above:

I-75I-719th & Vine9th & Walnut 8th & Vine8th & Walnut7th & Vine7th & Walnut 5th & Vine5th & WalnutI-75 N
I-75000000 10100
I-71000001 00000
9th & Vine100000 00000
9th & Walnut001001 00000
8th & Vine001000 00000
8th & Walnut000010 01000
7th & Vine000010 01000
7th & Walnut010000 00010
5th & Vine000000 10010
5th & Walnut000000 00000
I-75 N000000 00100

There are several things to notice about this matrix:

Our notion of connectivity changes somewhat when we talk about directed graphs:
In the directed graph example above,
I-75, 7th & Vine, 8th & Vine, 9th & Vine, I-75
is a walk,
I-75, 7th & Vine, 5th & Vine, I-75
is a semi-walk,
I-75, 7th & Vine, 8th & Vine
is a path and
I-75, 7th & Vine, 5th & Vine, 5th & Walnut, 7 & Walnut
is 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 matrix is a special case of a data structure called an array. Arrays can have any number of indices; that number is called the dimension of the array. A matrix is a 2-dimensional array; a 1-dimensional array is sometimes called a vector.

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 a linked 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 lot of 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.

We now move to one of the most interesting applications of the directed graph: the finite state machine.


Go to:Title PageTable of ContentsIndex

©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.