Minimum spanning trees

23090674189_03969b98aa_zIn our Young Entomologists classes the children tried the ‘muddy city’ problem from 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 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” by David C. Blanchard (Own work) [CC BY-SA 3.0 ( 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.

Insects in our life

What is the chemical formula for formic acid?

How long do butterflies live for?

Can the bodies of butterflies be furry, or only moths?

And did you know that a queen bee can lay up to 1500 eggs a day?

Skipper butterfly carrying a load of pollen grains. By Dr. Raju Kasambe (Own work) [CC BY-SA 3.0 (, via Wikimedia Commons
I have been starting off each session with the children asking questions or telling the whole group interesting facts about insects. Often I didn’t know the facts they tell me, and I don’t know the answers to the questions. I try to research them for the next time. I used Quora to find out the answer to the furry butterfly question, as I couldn’t find it easily myself.

In class 3, after the the Q&I session we looked at a great ‘bug poster‘ from

If you go on the website you can see a version of the poster and you can click on any picture to find out if the ‘bug’ is good or bad and what it does. (Note that some of the pictures take you to the same webpage and you might have to do a little bit of detective work to find out exactly what the creature in the picture is.)

This was a good way to start discussing good insects and bad insects, and how we might control them without using insecticide. We talked about parasites and parasitoids and the difference between them. We then started to make our own poster with words and pictures depicting how insects could be harmful or helpful.

In both classes I tried to conduct a lifecycle cut-and-paste activity. In the outdoor class, the wind, coupled with the restlessness of the children, made this rather tricky. I think we managed nevertheless to discuss the different stages of an insect life cycle. Some insects such as butterflies go through complete, marked, metamorphosis between larva and adult, and others go through gradual metamorphosis e.g. grasshoppers, where the young (known as a nymph) closely resembles the adult form. Talking about insects shedding their skins got us thinking about when insects were most vulnerable in their life cycle, and prompted another question about how long it takes for their skin to harden again. (It depends on how long the insect lives for. For some long-lived insects it could take 2 weeks.)

The next session was meant to be ‘Insects in the bush’ but we were put off visiting Stony Range by an aggressive nesting butcher bird, and our trip to Alan Newton Reserve in North Curl Curl was cut short by the start of an impressive storm. We retreated to the classroom and did some more insect drawings and discussed adaptations instead. Some children enjoy drawing insects, some are not very keen at all, and I admit that this class was not well planned. I think I should have an ’emergency lesson plan’ up my sleeve for next time we have bad weather.

More information

Friend or foe?‘ information from Museum Victoria.

More specific information about pollination, seed dispersal and bites and stings, all from the Australian Museum.

And an activity to test ant repellents, from Science Buddies.

Drawings of insects and insect life cycles

Butterfly life cycle

Ask a biologist: Complete metamorphosis and incomplete metamorphosis

Short videos and games about insect metamorphosis

Text-dense but very informative page about insect life cycles with a special section about parasitoids, and aphid life cycles including parthenogenesis.

Arthropods on the Understanding Evolution site. There’s a special bit about size restraints, particularly relating to moulting.