Digraphs and One Way Streets, Part I

One way mathematicians come up with new ideas is by modifying old ones - adding or taking away requirements and seeing what happens. In this section, we'll take away one part of the definition of a graph to come up with a whole new concept.

What You Should Learn

  • The technical definition of a graph and how it relates to a physical picture.
  • The names of the parts of a graph.
circuit board

One way signs are a real world situation "modeled" by a digraph.

A directed graph, also called a digraph, is a finite nonempty set V and an irreflexive relation R on V. The elements of V are called vertices. The elements of R are called directed edges or arcs.

So what's the difference between a graph and a digraph? It comes down to one word: reflexive. A graph's relation has to be reflexive where a digraph's doesn't. So if AB is an edge in a graph then BA must be an edge also. In a digraph it's possible for AB to be part of the relation where BA isn't.

Let's take a concrete example and look at it from both perspectives.

Let V = { v1, v2, v3, v4, v5 } and let R = { (v4, v2), (v3, v4), (v3, v1), (v3, v5), (v5, v3) }.

Notice that the elements of R do not come in pairs. For example, (v3, v4) is in R but (v3, v4) isn't.

graph 3

The picture to the right illustrates the graph from the technical side. Notice that all of the lines have arrows indicating the direction of the arc. You can get the direction from the definition of the digraph. The first letter in the pair is the starting point; the second letter is the ending point.

You should also notice that it is possible for an arc to go in both directions. The connection between v3 and v5, for example, is reflextive. If all of the arcs in a digraph are symmetric then the digraph is actually a graph.

Digraphs can be used to model any situation where the flow is one way. One way city streets are an obvious example. Water flowing through a sewer system is another example. City engineers can open and close valves to change the path taken by the water but regardless of their choices the water always flows in one direction - downhill.

Digraphs and One Way Streets, Part II >><< Graphs, Vertices and Edges, Exercises