Minimum spanning trees

23090674189_03969b98aa_zIn our Young Entomologists classes the children tried the ‘muddy city’ problem from csunplugged.org.They were trying to minimise the paving between a certain number of houses, while ensuring that each house was connected to each other. Read on to find out how this is connected to entomology!

I only recently discovered the csunplugged.org site, which takes key concepts from computer science and maths, and suggests hands-on activities for children to learn about these concepts. There is an e-book with all the activities which you can download for free from the site, or you can search for a particular concept and just download the activities relating to that concept.

If you have a map with various points that you have to visit, a ‘spanning tree’ is a route that connects all of those points so you can visit each of them at least once. There are usually many spanning trees for the same map, but a minimum spanning tree is the shortest route that connects all of the points.

Note that in the specialised area of mathematics known as graph theory, the map, points and route described above are known as a graph, vertices and path.

Other similar problems that are well known in mathematical circles are the travelling salesman problem, the seven bridges of Königsberg and the Chinese postman problem.

Think of how many networks there are in our society – road transport, power grids, water supply. Computers use pathfinding algorithms to find the minimum spanning trees in these networks and therefore make them more efficient. Also, routers in communication networks often have spanning tree protocols to avoid looping.

How on earth is this connected with entomology? I have been interested in minimum spanning trees since reading about Dr Tanya Latty‘s work on swarm intelligence in slime moulds and ants. Dr Latty is currently at the University of Sydney and she works in collaboration with researchers from many different disciplines, including computer scientists.

Ants have very small brains, and slime moulds don’t even have a brain at all, yet their simple behaviour can solve complex problems in a similar way to that of a computational algorithm. Get colonies of Argentine ants to connect three nests together and their resultant path will have a central hub, making the shortest possible path which connects the three points. (This is known as a Steiner tree, which is rather similar to a minimum spanning tree, just with extra vertices allowed if it makes the solution shorter.)

steiner_minimum_tree_med
“Steiner Minimum Tree” by David C. Blanchard (Own work) [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0)%5D via Wikimedia Commons

You can learn more about Tanya Latty’s work on the tvs show Enquiring Minds, where she was filmed as their insect expert. There’s more information about using collective behaviour to make decisions here, explained by Prof David Sumpter.

Visit the csunplugged site to see many more activities related to minimum spanning trees and related mathematical or computational problems.

Advertisements

Please add your comments below. I'd love to know what you thought about this post.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s