How to grow trees

Professor Robin Wilson

   I think that I shall never see
   A poem lovely as a tree.

Today you’ll see lots of lovely trees – family trees, chemical trees, sorting trees, linguistic trees, and many others, set in the context of the related area of graph theory.

You’ll also see ‘homeomorphically irreducible trees’, as featured in the film Good Will Hunting, where the mathematically gifted janitor (played by Matt Damon) was challenged to list all of them with ten vertices – a problem that (according to the film) had challenged MIT professors for two years, but which I regularly set to my undergraduate graph theory classes who can solve it without difficulty – but more of that later.

Also, though having nothing to do with trees, I’ll solve the Instantinsanityproblem of the four cubes – each cube has faces coloured red, blue, yellow and green, and the problem is to pile them up so that each of the four colours appears on each side. There are 82,944 ways of stacking the cubes, but only one way works, and we’ll use graph theory to find it.

Graph theory

For the purposes of graph theory, a graph doesn’t have its usual meaning – rather, it’s a diagram consisting of a number of points, which we callvertices (or nodes), and where certain pairs of vertices are joined by lines, called edges (or arcs) (see Fig. 1). The number of edges emerging from any vertex is called the degree of that vertex.

Graphs are a convenient way of illustrating objects and the connections between them. Familiar examples include road and rail networks, such as the familiar London Underground map where the vertices are the tube stations and the edges are the lines connecting them. Using this graph we can easily trace our way from any station-vertex to any other.

The origins of graph theory can be traced back to a problem arising in 18th-century Prussia. The medieval city of Königsberg was divided by the River Pregel into four parts, linked by seven bridges, and the Königsberg bridges problem was to go for a walk that crosses each of the seven bridges just once and returns to the start (se Fig. 2).

This problem was solved by Leonhard Euler, whose method is now usually recast in terms of graphs as follows. If we draw a graph with four vertices (corresponding to the land areas) and seven edges (corresponding to the bridges), then the problem is to draw this graph in one continuous line without repeating any edge (see Fig. 3). To see that this is impossible, note that whenever we enter a vertex (land area) we must be able to leave it by another edge (bridge), thereby contributing 2 to the degree of that vertex. It follows that all the vertex-degrees must be even, contradicting the fact that the Königsberg graph has degrees 3, 3, 3 and 5.

Graphs also arise in other puzzles, such as tracing a maze. If we represent each intersection of passageways in the Hampton Court maze by a vertex, and the passageways themselves by edges, then we obtain a graph in which we can see at a glance all the different ways of escaping from the maze.

Another well-known puzzle, which forms the basis for much current activity in graph theory, is to show that in any group of six people there are always at least three mutual acquaintances or at least three mutual non-acquaintances. To solve this we represent the people as vertices and draw red lines to indicate pairs who know each other, and green lines for those who don’t (see Fig. 4) – we need to show that in any colouring of the edges there is always a red triangle or a green one. To do so, we note that there are five edges out of each vertex, so at least three of them must have the same colour (say, red). But the triangle formed by the other ends of these edges must then contain a red edge (thereby forming a red triangle) or must consist of green edges that form a green triangle.

One of my favourite graphs concerns key-changes in music. If you listen to a change of key, it may either sound very natural (as the perfect fourth C to F) or may ‘jar’ (as the tritone C to F#). I’ve explained this by drawing a graph with 24 vertices corresponding to all the major and minor keys, and joining two vertices when the keys are closely related – this means that C is joined to F and G and to their relative minor keys. We can then see immediately from the graph how ‘close’ two given keys are, and how to get from one key to another.

Another use of graphs to depict situations relates to the phasing of traffic lights at a complicated road intersection. If we draw a graph in which the vertices correspond to streams of traffic and the edges correspond to compatible streams that can move through the intersection at the same time, then we can easily see from this graph how to plan a traffic-light sequence that maximises the total flow of traffic through the intersection.

Trees

We now turn our attention to trees. A tree is a connected graph (in one piece) with no cycles in it. There is just one tree with 1 vertex, one with 2 vertices, one with 3 vertices, two with 4 vertices (a straight line and a Y-shape), three with 5 vertices, and six with 6 vertices (see Fig. 5). Since we can build up any tree by starting with a single vertex and then successively add a new edge and a new vertex, it follows that in any tree, the number of vertices is always one more than the number of edges.

The ‘homeomorphically irreducible trees’ that featured in Good Will Hunting are simply trees in which no vertices have degree 2 – such trees are easy to construct, and we can easily use trial and error to solve Matt Damon’s problem of finding the ten such trees with 10 vertices.

Trees are very convenient for illustrating branching processes. The most familiar example is a family tree, showing successive generations of a family – this is a tree as long as there is no intermarrying. A related example is the tree of life, or dendrogram, representing evolutionary relationships between animal or vegetable species.

These are both rooted trees, in which one vertex is designated as the root and the others appear in levels below it (see Fig. 6) – graph theorists always seem to put their roots at the top! Examples of rooted trees include hierarchies of various types. Rooted trees can also be used to record the outcomes of experiments, such as the successive outcomes of tossing a coin, or the various moves in a game of strategy such as noughts-and-crosses or chess.

Another type of rooted tree is the sorting tree. One example arises from the sorting of books according to their Dewey decimal code. For example, codes of the form 5xx correspond to the physical and biological sciences, which are then subdivided into 50x (general science), 51x (mathematics), 52x (astronomy), 53x (physics), 54x (chemistry), and so on; these are then subdivided further – for example, 511.5 is graph theory and 511.6 is combinatorial analysis. Another sorting tree arises in the sorting of mail by postcode or zip code.

Noam Chomsky (MIT) and others have used rooted trees in linguistic analysis. A sentence such as Robin wears red socks can be split into subject and predicate, the latter can then be further split into verb and noun phrase, and the noun phrase is split into adjective and noun. Such trees can also be used to display ambiguities – for example, the sentenceCouncil rents rocket can be read in two different ways, giving rise to two different rooted trees.

An example in which the study of trees led to great savings in money arose around 1970 in connection with the design of a gas pipeline networkin the Gulf of Mexico. Here, the wellheads are connected by pipes of various diameters in a tree structure (as any cycles would add to the cost), but which one? The initial proposed tree structure would have cost about $210 million dollars. By a simple process of replacing one edge by another and recalculating the pipe diameters (which took about one second on the computers then available), savings of about two million dollars were effected. This replacement process was then repeated several times, by investigating the various ways in which the tree could be modified, and it led eventually to a saving of about ten million dollars in the total cost of the network. Who says that money doesn’t grow on trees?

Before turning to the historical origins of trees, I’d like to present one of my favourite examples of an unexpected use of graph theory – on the rigidity of rectangular frameworks, which is relevant to the construction of buildings and other rigid structures.

Suppose that we have a rectangular framework consisting of rods linked by pin joints, forming a pattern of square cells, so that the whole structure can move in the plane (see Fig. 7). We now brace some of the square cells so that parts of the framework become rigid while others are still free to move. The more braces we add, the more rigid the structure becomes, but it is very difficult to predict by looking at a given braced framework whether it is rigid or not.

To do this, we draw a graph in which the vertices correspond to the rows and columns of the framework, with an edge joining a row-vertex and a column-vertex whenever the cell in the corresponding row and column is braced. It turns out that if the resulting graph is connected (that is, in one piece), then the framework is rigid, but if the graph splits into smaller graphs, then it isn’t (see Fig. 8). Moreover, the appearance of a cycle in the graph shows that the corresponding part of the framework is over-braced (so that it stays rigid when we remove a brace), whereas if the graph is a tree then the bracing is a ‘minimum bracing’ – the framework is rigid, but the removal of any brace yields a non-rigid framework.

The origins of trees

Unlike some other parts of graph theory which have their origins in recreational problems (such as the bridges of Königsberg and the four-colour problem), early uses of trees arose from problems in the sciences – by Gustav Kirchhoff in his researches into electrical networks in the 1840s, and later by Arthur Cayley and James Joseph Sylvester in connection with the enumeration of chemical molecules.

Electrical networks

Suppose that we wish to find all the currents and voltages in an electrical network of resistors linked to a voltage source. Kirchhoff represented such a network by a graph in which the vertices correspond to the terminals and the edges correspond to the wires joining them. He then assigned arbitrary directions to the currents and stated his two famous laws, the voltage law and the current law. By applying the current law to each cycle in the network, he derived an equation relating the currents around that cycle. But some of the cycles prove to be redundant – they can be obtained by ‘combining’ other cycles – and the corresponding equations provide no new information. To lessen the work involved, Kirchhoff introduced the idea of a spanning tree, a tree that includes each terminal vertex of the network, and used it to get a ‘fundamental system of cycles’ that gives the necessary information about the currents without redundancy.

Chemistry

By the 1850s it was known that elements combine in fixed proportions to form chemical compounds, and formulas such as H 2O (water) and C 2H 5OH (ethyl alcohol) were known. But it wasn’t understood how the elements actually combine.

The answer is valency, which was developed independently by several people – Edward Frankland ( England ), Couper Scotland), Butlerov ( Russia ) and especially August Kekulé ( Germany ). In 1864, this was taken up by Alexander Crum Brown, who introduced graphic formulae – chemical graphs with atoms as vertices and chemical bonds as edges; the carbon, oxygen and hydrogen vertices have, respectively, degrees 4, 2 and 1, corresponding to the valencies of these atoms (see Fig. 9).

Using these graphs we can easily explain the phenomenon of isomerism, where different molecules with different properties have the same formula – for example, there are two molecules with formula C 3H 7OH: they differ in that the –OH part of the graph is joined to the middle carbon vertex in one molecule, and to an end-vertex in the other.

These ideas lead to the problem of finding the number of paraffins (oralkanes) with chemical formula C nH 2n+2. Their graphs are trees, since they have n + (2n+2) = 3n+2 vertices and ½{4.n + 1.(2n+2)} = 3n+1 edges. Similarly, any graph corresponding to an alcohol with formula CnH 2n+1OH is a tree.

Cayley originally became interested in trees in 1857, through a problem of Sylvester’s on the differential calculus. Cayley main concern was in counting rooted trees – which he did by using a ‘generating function’ of the form 1 + A 1x + A 2x 2 + …, where A n is the number of rooted trees with n branches – such a generating function enables us to keep track of all the terms in the sequence of A ns all at once by means of a single formula. Cayley found that cutting off the root gives several smaller rooted trees, leading to a recurrence relation from which each successive number A ican be found iteratively, one at a time.

Counting unrooted trees is a much harder problem, but Cayley eventually found a way of doing this – by starting at the middle of the tree and working outwards.

Cayley’s motivation for counting trees soon became that of enumerating chemical molecules – paraffins, alcohols, and others with a tree structure. Using his tree-counting methods Cayley managed to find the correct numbers of paraffins with up to 11 carbon atoms.

Much later, in 1889, Cayley solved the problem of enumerating trees withnlabelled vertices. There are three such trees with 3 vertices (see Fig. 10), sixteen with 4 vertices, and in general there are n n –2 with nlabelled vertices. Cayley presented the correct formula, but his proof was deficient.

Sylvester was also interested in chemistry. He had been fascinated by the use of graph-like pictures to depict molecules, and believed there to be a connection between such ‘graphic formulae’ and ideas from algebra. Indeed, in the middle of a paper in the American Journal of Mathematics, a journal that he’d just founded, he waxed eloquent:

Chemistry has the same quickening and suggestive influence upon the algebraist as a visit to the Royal Academy, or the old masters may be supposed to have on a Browning or a Tennyson. Indeed it seems to me that an exact homology exists between painting and poetry on the one hand and modern chemistry and modern algebra on the other …

Inspired by Frankland’s Lecture notes for chemical students, Sylvester and William Kingdon Clifford tried to associate with each atom (vertex) an algebraic expression called a ‘binary quantic’, and with each chemical molecule (graph) an ‘invariant’ of a system of binary quantics. This work was summarized by Sylvester in Nature in 1878. He described the correspondence:

The analogy is between atoms and binary quantics exclusively. I compare every binary quantic with a chemical atom … An invariant of a system of binary quantics … is the analogue of a chemical substance composed of atoms … and then said that:

Every invariant and covariant thus becomes expressible by a graph …

This is the very first appearance of the word graph in the graph theory sense.

Graph algorithms

There are a number of algorithms that involve the use of trees. We consider two problems that arise in operations research – the minimum connector problem and the travelling salesman problem.

Minimum connector problem

Suppose that we wish to connect a number of cities by links, such as canals, railway lines, or air routes. There must be enough links so that we can get from any city to any other (not necessarily in one step), but building canals is costly so we need to keep the total cost to a minimum. How can we do this?

An example with five cities, A, B, C, D, E, has links with the following lengths, or costs: AB: 6; AC: 4; AD: 8; AE: 2; BC: 5; BD: 8; BE: 6; CD: 9;CE: 3 and DE: 7 (see Fig. 11). How do we find our minimum connector?

We can experiment: taking BC, CD, DE and EA we link all the cities, with total length 2 + 7 + 9 + 5, which is 23; taking AB, AC, AD, and AE we again link all the cities, but with total length 6 + 4 + 8 + 2, which is 20 – quite an improvement. But is this the best we can do?

Notice that each of these solutions is a tree – it contains no cycles: for if there were a cycle, we could decrease the total length by removing any one link from the cycle. So how do we find the right tree structure? By Cayley’s theorem there are 5 3 = 125 possible trees joining these cities, so we can’t use trial and error. Worse still, the number of trees increases dramatically with extra cities: over 1000 trees for six cities, and 100 million for ten cities. Since most practical examples have hundreds of cities, we need an algorithm to solve this problem.

The algorithm we use is called the greedy algorithm, since at each stage we’re ‘greedy’ and choose the shortest possible link available. So here we start with link AE (length 2). Then CE (length 3). We can’t now choose AC(length 4) since that gives a cycle, so we use BC (length 5). What next? Each of the links of length 6, AB and BE, gives a cycle, so we go to DE (length 7). This completes the tree, so we stop – the cities are now all linked by a tree of total length 2 + 3 + 5 + 7 = 17. This is a great improvement on what we had before, and turns out to be the best possible solution.

In fact, the greedy algorithm always gives a minimum connector – however many cities there are. We just model the situation by a network, and program a computer to make the choices. Moreover, it’s anefficientalgorithm, taking very little computer running time – it’s at worst a multiple of the square of the number of cities, so if the number of cities increases ten-fold, the computer time goes up by a factor of only 100, which is very efficient.

The other problem is the travelling salesman problem. Here, a salesman wishes to sell his wares in a number of cities, so he visits them all and then returns to his starting point. How can he plan his route so as to minimise the total distance?

One route is to go round the outside: A - B - C - D - E and back to A, with total distance 29. Or he could follow the star-shaped route A - C -E  - B -D - A – still distance 29. The route A - C - E - D - B - A is slightly better, with length 28. The best possible route is A - D - B - C - E - A, with length 26, but to find it I had to use trial and error: no known efficient algorithm is guaranteed to produce it – but neither has anyone ever proved that no such efficient algorithm can exist.

Instant insanity

To conclude, I’d like to return to the cube-stacking problem known asinstant insanity.

We solve this problem by representing each cube by a graph with four vertices, R, B, G and Y, one for each colour. In each graph, two vertices are joined if and only if the cube in question has the corresponding colours on opposite faces (see Fig. 12).

We next superimpose these graphs to form a new graph G. A solution of the puzzle is obtained by finding two subgraphs H 1 and H 2 of G. The subgraph H 1 tells us which pair of colours appears on the front and back of each cube, and the subgraph H 2 tells us which pair of colours appears on the left and right. To this end, the subgraphs H 1 and H 2 must have the following properties:

(a) each subgraph contains exactly one edge from each cube; this ensures that each cube has a front and back, and a left and right, and the subgraphs tell us which pairs of colours appear on these faces.

(b) the subgraphs have no edges in common; this ensures that the faces on the front and back are different from those on the sides.

(c) each subgraph is regular of degree 2; this tells us that each colour appears exactly twice on the sides of the stack (once on each side) and exactly twice on the front and back (once on the front and once on the back).

The solution can now be read from these subgraphs.

© Professor Robin Wilson, Gresham College, 01 February 2006