Networks

New Zealand

Level 7 - NCEA Level 2

Lesson

Sometimes it is going to be very impractical to find a minimal spanning tree by eye. The following network represents a **mycorrhizal** nutrient transfer system:

A severe drought is affecting the area, so only the most essential connections can be sustained by the fungus. What is the **shortest total distance** that the mycorrhizal network needs to spread itself across, while still making sure that every plant is connected to every other one?

We need to find the minimal spanning tree. This particular network has $416$416 spanning trees, which one is minimal? Feel free to find them all and add up all their weights, but it’s going to take a very long time.

Instead, we’re going to use a procedure called **Prim’s Algorithm** to find the minimal spanning tree without having to find **all** the spanning trees. The algorithm was first created by Vojtěch Jarník, a Czech mathematician, in 1930. Both Robert Prim (in 1957) and Edsger Dijkstra (in 1959) independently rediscovered it, though Prim’s work popularised its use.

We begin by **picking a vertex**, any vertex will do. Let’s say we pick $F$`F`. We then **highlight the lowest weight edge** coming out of $F$`F`:

We then **add this edge**, and the vertex on the other side, to our spanning tree:

Then we do the same thing again! Highlight the edge of lowest weight coming out of our spanning tree:

We then add that edge, and its vertex, to the spanning tree:

Once again, we highlight the lowest weight edge coming out of the spanning tree:

This time, there are **two** candidates! Both $DC$`D``C` and $DF$`D``F` have weight $12$12. We can **pick either one** at this point:

The lowest weight edge coming out of the spanning tree is still the weight $12$12 edge $DF$`D``F`:

However, we are going to **reject this edge**, since adding it to our spanning tree would **create a cycle**, and trees can’t have cycles.

We won’t ever consider the edge $DF$`D``F` again. So we move on to highlighting the next lowest weight edge:

This edge doesn’t create a cycle, so we add it in to the growing spanning tree:

The next lowest weight edges are all weight $14$14 so we highlight them all:

Once again, we **reject **the edge $DB$`D``B` since it would create a cycle:

That leaves us with **two choices**:

We are free to **pick either** of these. We add in the edge and the vertex, growing the spanning tree by one vertex every step:

Instead of going back to the edge $EG$`E``G` of weight $14$14, we now have an edge connected to our spanning tree of lower weight:

We add that in as before, and highlight the lowest weight edge connecting the spanning tree to our final vertex:

We add this edge and vertex in to the network, completing the procedure:

We can delete the unused edges for a clearer picture of our final result:

Our fungus spanning tree has grown from the vertex $F$`F` to cover every plant in the area, and it covers $12+10+10+13+14+8+7=74$12+10+10+13+14+8+7=74 metres in total.

This procedure is **guaranteed** to find the minimal spanning tree every time. Much easier than finding all the spanning trees and adding up all their weights! Here’s a summary of the procedure.

Prim’s algorithm:

**Pick any vertex**to start the spanning tree.- Locate the
**lowest weight edge**connected to the spanning tree. - If this edge would create a cycle,
**reject**it. - If there is
**more than one edge**with the lowest weight,**pick any**of them. **Add this edge**and the vertex at the other end to the spanning tree. If all vertices are part of the spanning tree, stop. Otherwise,**repeat from step 2**.

Choose appropriate networks to find optimal solutions

Apply network methods in solving problems