These trees are different to the binary trees we saw earlier, though they still do not have loops or branches that run across each other. The problem here is to devise a network or tree that spans all the nodes in an area using the shortest possible route and therefore the least amount of materials.
This problem might be applied to, for example, a road network such as motorways, a rail network, a series of connecting aeroplane flights, a computer network or a utility such as gas or electricity moving from house to house.
Work in pairs. You should have a sheet of graph paper, a pencil and a ruler each. On one sheet of paper plot some points at various intervals across the graph paper as if they were towns on a map or houses in a neighbourhood with no links between them. Make a copy of the points on the second sheet. Each member of the pair should start at a different point and then look for a way to build the shortest route to link all places.
Compare the length of the routes you have created. Do you think you could do better? How? Make two more copies and complete a second tree using the 'greedy algorithm'.
What are the advantages and disadvantages of a minimal spanning tree? What if the links were roads, how useful would they be?
Can you see any practical uses for this technique in the world of computer networking? What general principle would you consider when connecting computers together with, say, optical fibre? How does the minimal spanning tree approach compare with the way the Internet is linked together? (Take a look at this.) UK USA.
Practical: Draw a sketch map of the UK and mark on it the major cities (London, Leeds, Bristol, Manchester, Birmingham, Newcastle, Liverpool, Cambridge, Glasgow, Edinburgh). Add lines to the sketch that connect the cities with the minimum length of cable. How effective would this network be? Draw an alternative network that would improve connectivity for users. Suggest one additional link to the network that would improve connectivity for a major city. (All of this could be applied to the motorway network.)
