Embedded Files
Efficiently linking all the nodes together
Efficiently linking all the nodes together
Background
Background
In 1926, the mathematics of connecting all the nodes in a network efficiently was first investigated by a Czech mathematician called Otakar Borůvka. He was looking for the most efficient way to connect the towns of Moravia (part of Czechoslovakia at the time) with a new electrical supply network. Efficiency meant minimum cost; he was looking for the cheapest way to connect the towns together.
Borůvka largely misses out on credit for his work, as does Vojtěch Jarník, another Czech mathematician who found a similar algorithm in 1930. The algorithms most commonly known for this network problem are Prim's algorithm (which is just the same as Jarník's) and Kruskal's algorithm; both named after American mathematicians in the 1950's.
Otakar Borůvka
Definitions
Definitions
A tree is a connected network with no circuits in it. There is no particular beginning point or end point for a tree; just a collection of edges between nodes, and no circuits. This means that in a tree, there is exactly one one way to get from any node to any other node. If there was more than one way, there would be a circuit.
Here are a few examples of trees. Notice that a path (with no 'branching') is still a tree.
If a tree has N nodes, it must have N - 1 edges.
A tree with 6 nodes (and 5 edges).
This tree has a central node that all others are connected directly to - most trees don't.
This path is also a tree, even though it doesn't "branch".
A spanning tree for a network is a tree that uses all of the nodes of the network, and some of the edges. It's a collection of just enough roads that you can drive from any start point to any end point; but probably not with the shortest route (more on that, later).
Every connected network has lots of possible spanning trees. The total of the weights of the edges in a spanning tree is the total weight.
A spanning tree with the minimum total weight is called a minimum spanning tree.
In the roads context, we're looking for the shortest collection of roads that joins all the towns together.
Algorithms for Minimum Spanning Tree (MST)
Algorithms for Minimum Spanning Tree (MST)
There are two approaches for finding a minimum spanning tree. It doesn't matter much which you use, although sometimes one is faster than the other.
The first adds small weight edges into a spanning tree until it is compete.
The second removes large weight edges from the network until it is a spanning tree.
Kruskal's Algorithm
Kruskal's Algorithm
- Find the smallest weight edge in the network.
- Add the edge to the spanning tree, unless this would create a circuit.
- While the network is not a spanning tree, return to step 1.
Notice that we have to be careful to make a tree; there can't be any circuits added along the way.
Sometimes, some small weight edges can't be in the tree.
A worked example is below.
Kruskal.pdfCircuit-Delete Algorithm
Circuit-Delete Algorithm
- Find a circuit in the network.
- Remove the largest weight edge in the circuit.
- While the network is not a spanning tree, return to step 1.
Notice that you can only remove a large weight edge if it is in a circuit.
Sometimes, some large weight edges have to be in the tree.
A worked example is below.
circuit-delete.pdfThere are other similar algorithms, including one like Kruskal's algorithm that builds a tree which expands through the network. At each step, it's a tree, growing into a minimum spanning tree. This is called Prim's algorithm.
All of these algorithms are greedy - they choose the smallest weight edge to add, or the biggest weight edge to remove.
Checkpoint
Checkpoint
- How many edges will there be in a spanning tree of the network?
- What is the first edge added by Kruskal's algorithm to a minimum spanning tree?
- What is the last edge added by Kruskal's algorithm to a minimum spanning tree?
- Which edge would the circuit-delete algorithm remove from the circuit B-C-D-E-B?
- What is the smallest weight edge NOT in the minimum spanning tree?
- What is the largest weight edge in the minimum spanning tree?
Exercises
Exercises
Use a copy of the exercise sheet and draw each network, then find a minimum spanning tree.
Exercise.pdfTasks
Tasks
100 Acre Wood
100 Acre Wood
Task 3: Christopher Robin decides that some tracks need to be patrolled daily to be kept clear of Woozles. The shortest total length of track should be patrolled, with all locations should be accessible from his house.
Find an optimal list of tracks to be patrolled, and suggest how four friends (Christopher Robin, Kanga, Owl and Rabbit) could best patrol these tracks.
100acre.pdfSherwood Forest
Sherwood Forest
Task 3: The Prior of Newstead Abbey (near Mansfield) is an important landowner, who wants to keep roads between markets safe for his tenants. Recommend a web of roads that should be kept safe, and tell him how much longer this web would need to be if the three roads through Sherwood Forest are not included (those roads shown in the diagram).
sherwood.pdfThe Shire
The Shire
Task 3: Peregrin decides to widen some of the roads of The Shire, to improve commerce across the region. He wants to widen some the roads linking the towns (marked with black circles) and also the town of Bree. Firstly, recommend the shortest system of roads that should be widened. Secondly, suggest (with reasons) which two roads might be widened next.
shire.pdfInvestigations
Investigations
(A) Which is faster: Kruskal's algorithm or the circuit-delete algorithm? What does this depend on?
(B) Imagine a network with one edge weight 100, and all the other edges smaller (positive) weights. Could the weight 100 edge be part of a minimum spanning tree?
Key words: tree, spanning tree, minimum spanning tree, circuit, algorithm, circuit-delete algorithm
Google Sites
Report abuse