Minimum Spanning Trees and Greedy Algorithms (VCE SSCE General Mathematics): Revision Notes

Minimum Spanning Trees and Greedy Algorithms

Introduction

When working with networks, we sometimes need to connect all points (vertices) together using the minimum amount of resources. This is different from finding the shortest path between two specific points.

Imagine connecting several towns to a water supply network. Rather than creating direct connections between every pair of towns, we want to minimise the total length of water pipes needed while still ensuring every town gets connected. This type of problem can be solved using a mathematical structure called a tree.

Trees

What is a tree?

A tree is a connected graph that has no cycles, no multiple edges, and no loops.

Key properties of trees:

• All vertices are connected
• There are no closed loops or circuits
• No two vertices are connected by more than one edge
• No vertex connects back to itself

The first two graphs shown are trees because they connect all vertices without creating any cycles. The third graph is not a tree because it contains a loop (a vertex connecting to itself), multiple edges between vertices, and cycles (closed paths).

The vertex-edge relationship

Trees have a special mathematical relationship between vertices and edges.

For example:

• A tree with $8$ vertices has $7$ edges
• A tree with $11$ vertices has $10$ edges

Spanning trees

What is a spanning tree?

A spanning tree is a tree that connects all vertices in a connected graph.

When you have a graph with multiple edges, you can often create several different spanning trees by removing some edges while keeping all vertices connected.

Graph 2 and 3 above are different spanning trees of Graph 1.

Finding spanning trees

To find a spanning tree for a graph:

1. Count the vertices. If there are $n$ vertices, your spanning tree needs exactly $n - 1$ edges.
2. Remove edges from the graph while ensuring:
   • All vertices remain connected
   • No cycles are created
   • No multiple edges or loops remain
3. Multiple spanning trees usually exist for any given graph.

Minimum spanning trees

What is a minimum spanning tree?

For weighted graphs (where edges have numerical values representing distance, cost, time, etc.), we can calculate the total weight of each spanning tree.

A minimum spanning tree is a spanning tree with the smallest possible total weight.

To find the length of a spanning tree, add up all the edge weights in that tree.

For example, if a spanning tree includes edges with weights $5$, $4$, $2$, $1$, $5$, $4$, and $1$:

$\text{Length} = 5 + 4 + 2 + 1 + 5 + 4 + 1 = 22 \text{ units}$

Real-world applications

Minimum spanning trees solve practical problems where we want to minimise:

• The amount of cable needed for a computer network
• The length of water pipes for a housing estate
• The time needed to complete a project
• The cost of connecting locations

In each case, we want every location connected using the minimum total resource.

Algorithmic methods for determining minimum spanning trees

What is an algorithm?

An algorithm is a set of step-by-step instructions for solving a problem or completing a task.

In everyday life, a recipe is an algorithm. In mathematics, long division follows an algorithm.

Prim's algorithm

Prim's algorithm provides a systematic way to find a minimum spanning tree for a weighted graph.

Steps for Prim's algorithm

1. Choose any starting vertex.
2. From this vertex, select the edge with the lowest weight. If multiple edges have the same weight, choose any. This edge and the two vertices it connects form the beginning of your minimum spanning tree.
3. Look at all edges connected to vertices already in your tree. Choose the edge with the lowest weight that doesn't create a cycle (ignore edges that would connect the tree back to itself). Add this edge and its new vertex to your tree.
4. Repeat step 3 until all vertices are connected.
5. Calculate the total weight by adding all edge weights in your tree.

Worked example: Prim's algorithm

Kruskal's algorithm

Kruskal's algorithm is an alternative method for finding minimum spanning trees.

Difference from Prim's algorithm

Steps for Kruskal's algorithm

1. Choose the edge with the smallest weight as your starting edge. If multiple edges share the smallest weight, choose any.
2. From the remaining edges, select the edge with the smallest weight that doesn't form a cycle. If multiple edges share the smallest weight, choose any.
3. Repeat step 2 until all vertices are connected. You now have a minimum spanning tree.
4. Calculate the total weight by adding all selected edge weights.

Worked example: Kruskal's algorithm

Notice that both Prim's and Kruskal's algorithms found minimum spanning trees with the same total weight, though the specific edges selected may differ.

Greedy algorithms

What is a greedy algorithm?

A greedy algorithm solves optimisation problems by making the best choice at each step, hoping this leads to the best overall solution.

Prim's and Kruskal's algorithms are both greedy algorithms because:

• At each step, they choose the edge with the smallest available weight
• They don't reconsider earlier decisions
• They build toward a solution step-by-step

Characteristics of greedy algorithms

Dijkstra's algorithm for shortest paths (Extension)

Dijkstra's algorithm is another greedy algorithm, but it finds the shortest path between two specific vertices rather than a minimum spanning tree.

Steps for Dijkstra's algorithm

1. Assign the starting vertex a value of zero and circle it.
2. For each vertex connected to the circled vertex, assign a value equal to the edge weight connecting it to the starting vertex. Circle the vertex with the lowest assigned value.
3. From the newly circled vertex, assign values to connected vertices by adding the edge weight to the circled vertex's value. If a vertex already has a value and the new value is smaller, replace it. If a vertex is already circled, don't change its value. Circle the uncircled vertex with the lowest value.
4. Repeat step 3 until the destination vertex is circled. The assigned value of the destination vertex is the length of the shortest path.
5. Find the shortest path by backtracking: Start at the destination and work backward through circled vertices, choosing edges where the vertex value minus the edge weight equals the previous vertex value.

Remember!