Graphs

A tree is a special case of a more general structure called a directed graph. A graph has nodes, which in the context of graph theory are usually called vertices, and arrows, which in this context are called edges. Note that this usage of the word “graph” has no relation at all to the graph of a function.

There are also undirected graphs, where the edges that connect vertices don’t have a preferred direction.

Graphs appear in a lot of contexts, and we’ll see them again in later chapters. Here I’ll just give two examples, one of a directed graph and one of an undirected graph.

One common use of graphs is in understanding the structure of computer programs. The call graph of a program shows which functions call which. I wrote the following Racket program, for example, to solve Max Bezzel’s classical problem of finding all configurations of 8 queens on a chessboard such that none of them can reach any of the others in a single move.

#lang racket
(require srfi/1)
(define (id x) x)
(define (curry f arg1) (lambda (arg2) (apply f (list arg1 arg2))))
(define (rcurry f arg2) (lambda (arg1) (apply f (list arg1 arg2))))
(define (interval a b) (unfold (curry < b) id (curry + 1) a))
(define (shift slope s)
  (if (null? s)
      '()
      (cons (car s) (map (rcurry + slope) (shift slope (cdr s))))))
(define (duplicates? s)
  (any (lambda (t) (member (car t) (cdr t))) (unfold null? id cdr s)))
(define (okay? slope s) (not (duplicates? (shift slope s))))
(define (queens n)
  (filter (curry okay? 1)
          (filter (curry okay? -1)
                  (permutations (interval 1 n)))))

This in fact solves the problem for a chessboard of arbitrary size, not just the classical one of size eight. I’m not going to explain how it works, but there are eight functions defined and the first step towards understanding how this works would be to see which functions call which other functions, which is described by the call graph in the figure.

For an example of an undirected graph we consider a different classical puzzle, first posed by Alcuin of York:

Homo quidam debebat ultra fluvium transferre lupum, capram, et fasciculum cauli. Et non potuit aliam navem invenire, nisi quae duos tantum ex ipsis ferre valebat. Praeceptum itaque ei fuerat, ut omnia haec ultra illaesa omnino transferret. Dicat, qui potest, quomodo eis illaesis transire potuit?

English was in fact Alcuin’s native language but it probably wouldn’t have helped you very much if had written this in English rather than Latin since he died a little over twelve centuries ago and English has changed quite a bit since then. Here’s my own rough translation:

A man needed to transport a wolf, a goat and head of cabbage across a river. The only boat he could find could not accommodate two of these. The task, then, was to transport all of them safely. Say, if you can, how they all managed to cross safely.

As with most applied problems, we are give a statement which is missing some important information, which we will have to fill in. We must, for example, give a precise meaning to the word “safe”. Wolves eat goats. This practice is, from the point of view of the goat, unsafe.Goats eat cabbage. This practice is, from the point of view of the cabbage, unsafe. Of course we need to state all the negative assumptions as well.Of course we need to state all the negative assumptions as well. Wolves don’t eat cabbages. Cabbages don’t eat anything. Nothing eats wolves. Nothing eats itself. In Alcuin’s time the vast majority of the population lived from agriculture. These facts must have been obvious to his readers. In our modern urban world it is better to make these assumptions explicit. There is an additional assumption here, which, while not necessary to the formulation of the problem, is required for it to make sense. Wolves, goats and heads of cabbage are similar in size and shape, at least as far as fitting in boats is concerned. This makes me suspect that Alcuin wasn’t really any more agriculturally inclined than I am. There is another implicit requirement in the problem, that the man and boat always travel together. We could add this also to the statement of the problem, but there is a better option. Do we really need both the man and the boat? Physically, of course we do. Mathematically, one of them is redundant, precisely because they always travel together. It doesn’t matter much which we keep, but I will choose the boat.

We can now write a more precise form of the problem:

• We have a boat, cabbage, goat and wolf on one bank of a river.

• We want the boat, cabbage, goat and wolf on the other bank of the river.

• The allowed operations consist of transferring the boat and at most one of the other three from either bank to the other, without leaving the goat with either the wolf or the cabbage on opposite bank from the boat.

We can illustrate this with an undirected graph, in the sense described above, where the vertices represent the possible states of the system, i.e. who is on which bank, and the edges represent the allowed transitions. There are \({ 2 ^ 4 }\) possible ways to assign the boat, cabbage, goat and wolf to a river bank but six of those violate our safety constraint, leaving 10 vertices. Their labeling should be more or less self-explanatory. The symbol ‖ represents the river, and b, c, g, and w stand for “boat”, “cabbage”, “goat” and “wolf”, respectively. There should be an edge connecting each pair of vertices where the boat and at most one of the cabbage, goat or wolf move from one bank to the other.

Once you have drawn the graph it’s easy to find a solution to the problem. There are in fact exactly two solutions with the minimal possible number of crossings, which is seven. Of course with more realistic assumptions the set of solutions might be larger.

We will meet more practical applications of graphs later.