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,

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 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:

M_{i, 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 M_{i, j} is the number of arcs from vertex i to vertex j, describes the directed graph above:

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

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

There are several things to notice about this matrix:

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.

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

a walk through 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 path is still a walk with no repeated vertices, and a

"semi-path" is a semi-walk with no repeated vertices.

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:

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.

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

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

Go to: Title Page Table of Contents Index

Please send comments or suggestions to the author.