Sunday, 10 June 2012

A tree which is not a tree

Graph theory is perhaps my favourite area of mathematics.  It features diverse and appealing modes of reasoning, and many of the results are relatively accessible,  rather than requiring a lot of theory.  
A graph-theory tree
tree is a special kind of graph, like that above (the numbers serve only to identify the vertices).  Technically a connected graph is a tree if there is exactly one path connecting any two vertices, or equivalently the graph contains no cycle. In lay terms this means a diagram where points are joined by such a way that there is no loop.  The branching is like the branches of a tree (in the natural sense of the word) or of a family tree, as one sees in the diagram below, where one of the vertices is chosen as a root.
Rooted Tree

There are lots of results one can prove about graph-theoretical trees.  For example, a tree with n vertices must have exactly n-1 edges.  Trees are particularly useful in computer science.  But what I am interested in today is the definition.  

Books like Robin Wilson's excellent Introduction to Graph Theory motivate the definition by referring to family trees and botanical trees. Now there is a nice sycamore tree in our garden:

Our sycamore tree

But this is not a tree in the graph theory sense!  It contains a cycle:

Two squirrels could climb to the top of the tree taking different routes!  And that's impossible in a graph which is a tree, where there is only one route between any two points.

So what's gone wrong?  Why is my tree not a tree?  Why does the mathematical definition which seeks to encapsulate the "tree-ness" of trees, exclude this perfectly respectable specimen of a tree in our garden?

Well, mathematics is about abstraction.  The definition of "tree" abstracts something typical of real trees, which does reflect the nature of branching (our sycamore is slightly unusual).  It leads to a very rich branch of graph theory, with many applications.  So it's a good definition.  (But it doesn't exactly fit family trees either.  If you go back a few generations you get connections which give loops, when the same person is an ancestor in two different lines.  Otherwise we would each have far more ancestors than all the humans who have ever lived.)

Here's another illustration.  If I take a square piece of paper, it has four corners.  Let's get rid of the corners by cutting them off with scissors (cutting off a triangular piece at each corner).  I've taken four away from four: mathematically I might expect to have zero corners left, but in fact I have eight since the remaining paper forms an octagon.  So 4-4=8 in this situation.  (Peter Flom's blog has some other examples where 2+2 is not 4.)

So does maths fail?  No.  When I was younger I'd have felt that these examples of arithmetic failure were contrived, obviously artificial and not to be taken seriously.  I now think I was wrong.  These are real examples: it's mathematics that is contrived.  We abstract the rules of arithmetic from a world in which they don't always apply, to create a system which is enormously useful.  The power of mathematics comes from simplifying the real world.  The mathematical idea of a tree is powerful, even if it excludes some legitimate trees.  Arithmetic is powerful even if it doesn't apply to some real-life situations. 

So it's amusing that our sycamore tree is not a tree, but it isn't a flaw in graph theory!

No comments:

Post a Comment