Welcome to Algorithms on Graphs!
Welcome to one of the most practical and visual areas of Further Mathematics: Algorithms on Graphs. Have you ever wondered how Google Maps instantly finds the fastest route to your destination, or how telecommunications companies connect broadband across the country using the minimum amount of expensive fiber-optic cable? That is exactly what you are about to master!
An algorithm is simply a step-by-step set of precise instructions designed to solve a specific problem. In this chapter, we will look at how algorithms help us find optimal connections, shortest paths, and efficient routes across networks.
Don't worry if this seems a bit abstract at first! The methods in this module are logical, highly structured, and follow predictable patterns. Once you get the hang of the step-by-step recipes, you will find these questions among the most reliable marks in your exam.
---1. Quick Review: Essential Graph Terminology
Before diving into the algorithms, let's make sure we share the same vocabulary:
• Vertex (or Node): A point or location in a network, usually denoted by a capital letter such as \(A\), \(B\), or \(C\).
• Edge (or Arc): A line connecting two vertices.
• Weight: A numerical value assigned to an edge, representing a real-world quantity such as distance, cost, time, or capacity.
• Degree (or Valency): The number of edges connected to a particular vertex. For instance, if vertex \(A\) is connected to \(3\) edges, its degree is \(3\) (an odd vertex).
• Path: A sequence of connected edges where no vertex is visited more than once.
• Cycle (or Circuit): A closed path that starts and finishes at the same vertex, with no other repeated vertices.
• Tree: A connected graph that contains no cycles.
• Spanning Tree: A tree that connects all vertices of a graph together.
Crucial Golden Rule of Trees: If a connected graph has \(n\) vertices, any spanning tree will have exactly \(n - 1\) edges. For example, a network connecting \(6\) towns requires exactly \(6 - 1 = 5\) edges to form a spanning tree.
---2. Minimum Spanning Trees (MST)
A Minimum Spanning Tree (MST) is a spanning tree whose total sum of edge weights is as small as possible. Imagine you are connecting several computer servers: you want every server to communicate with every other server, but you want to lay the minimum total length of cable.
There are two primary algorithms to find an MST: Kruskal's Algorithm and Prim's Algorithm.
Kruskal's Algorithm (The "Cheapest Edge First" Approach)
Kruskal's algorithm is an edge-based method. Think of it like bargain hunting: you always pick the cheapest available edge, no matter where it is, provided it does not create an unwanted loop (cycle).
Step-by-Step Procedure:
1. List all the edges in the graph in ascending order of weight (from smallest to largest).
2. Select the edge with the lowest weight and add it to your tree.
3. Move to the next lowest edge. Add it to your tree unless it forms a cycle with the edges already chosen. If it forms a cycle, reject it.
4. Repeat this process until you have selected exactly \(n - 1\) edges (where \(n\) is the total number of vertices).
Analogy: Kruskal's algorithm is like building small islands of connections that gradually join up into one big continent.
Prim's Algorithm (The "Growing Network" Approach)
Prim's algorithm is vertex-based. Instead of picking edges from all over the graph, you start at one vertex and let your tree grow outward by always adding the nearest unconnected vertex.
Step-by-Step Graphical Procedure:
1. Choose any starting vertex (the exam question will usually specify one).
2. Look at all edges connecting a vertex already in your tree to a vertex not yet in your tree.
3. Pick the edge with the smallest weight. Add this edge and the new vertex to your tree.
4. Repeat until all vertices are included (i.e., you have chosen \(n - 1\) edges).
Prim's Algorithm Using a Distance Matrix (Tabular Form):
Exam questions frequently ask you to apply Prim's algorithm to a matrix of edge weights. Here is the foolproof method:
1. Choose the starting vertex. Number its column as 1 and cross out its row.
2. In the numbered column(s), find the smallest uncrossed value.
3. Circle this value. The row containing this circled value indicates the next vertex to add.
4. Number the new vertex's column with the next sequential integer (e.g., 2, 3, etc.) and cross out its row.
5. Repeat by finding the smallest uncrossed entry among all numbered columns until every row is crossed out and \(n - 1\) edges have been circled.
Comparing Kruskal's and Prim's Algorithms
• Kruskal's: Inspects individual edges across the entire graph. Edges do not need to be connected to each other during the intermediate steps.
• Prim's: Always maintains a single connected tree that grows step by step.
• Both: Always produce a minimum spanning tree with the same total minimum weight, though the specific edges chosen may differ if there are tied edge weights.
Key Takeaway: For a graph with \(n\) vertices, stop when you have selected \(n - 1\) edges. Always list the edges chosen in order and state the total weight by summing their values.
---3. Dijkstra's Algorithm (Shortest Path)
While MST algorithms find the cheapest way to connect all vertices, Dijkstra's Algorithm finds the shortest path between one specific starting vertex (the source) and all other vertices in the network.
Understanding the Node Labels
At each vertex, you will draw a standard working box with three sections:
• Vertex Name / Identity (e.g., \(A\), \(B\), \(C\))
• Order of Labelling: The step number at which this vertex was permanently fixed (\(1, 2, 3, \dots\)).
• Final (Permanent) Value: The true shortest distance from the start vertex to this vertex.
• Working Values: Temporary potential distances that get updated as you explore new routes.
Step-by-Step Procedure for Dijkstra's Algorithm
1. Initialise: Give the starting vertex a permanent value of \(0\) and label order \(1\). All other vertices currently have no permanent values.
2. Update Working Values: For the vertex you just made permanent, look at all directly connected neighbours that do not yet have a permanent label. Calculate:
\(\text{New Distance} = \text{Permanent Value of Current Vertex} + \text{Weight of Connecting Edge}\)
If this new distance is less than any existing working value at that neighbour, write it down.
3. Select the Minimum: Scan across all vertices in the graph that do not yet have a permanent label. Find the smallest working value.
4. Make Permanent: Make this smallest value the permanent label for that vertex, and assign it the next order number.
5. Repeat: Continue updating working values and making the smallest permanent until the destination vertex receives its permanent label (or all vertices are made permanent).
How to Trace the Shortest Path (Backtracking)
To find the actual route (the path) rather than just the numerical distance:
1. Start at the destination vertex.
2. Move backward to a preceding connected vertex \(U\) if and only if:
\(\text{Final Label of Current Vertex} - \text{Weight of Edge to } U = \text{Final Label of } U\)
3. Continue stepping backward until you reach the start vertex. Reverse the sequence to state the shortest path from start to finish.
Common Mistake to Avoid: Never change a permanent label once it has been assigned! Permanent values are final. Only working values can be added and replaced.
Key Takeaway: Dijkstra's algorithm is greedy: at every step, it locks in the vertex with the smallest provisional distance, guaranteeing the optimal shortest path.
---4. Route Inspection Problem (Chinese Postman Problem)
Imagine a postman delivering mail who must walk along every road (edge) in a neighbourhood at least once, before returning back to the sorting office (starting vertex). To save energy, the postman wants to minimise the total distance walked.
Eulerian and Semi-Eulerian Graphs
The problem depends directly on the degrees of the vertices:
• Eulerian Graph (All vertices have EVEN degree): An Eulerian trail exists that traverses every edge exactly once and returns to the start. The minimum route length is simply the sum of all edge weights.
• Semi-Eulerian Graph (Exactly TWO vertices have ODD degree): A trail exists that traverses every edge once, starting at one odd vertex and finishing at the other.
• Non-Eulerian Graph (More than two vertices have ODD degree): Some edges must be repeated.
Did you know? In any undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges (\(\sum \text{degrees} = 2E\)). Consequently, the number of odd-degree vertices is always even (e.g., \(0, 2, 4, 6\dots\)).
Standard Algorithm for the Route Inspection Problem
When there are odd vertices, the goal is to duplicate the set of paths between pairs of odd vertices that adds the minimum extra weight.
Case 1: Exactly 2 Odd Vertices (say \(A\) and \(B\))
1. Find the shortest path between \(A\) and \(B\).
2. Repeat (duplicate) the edges along this shortest path.
3. \(\text{Minimum Total Length} = \text{Sum of all edges in graph} + \text{Length of shortest path between } A \text{ and } B\).
Case 2: Exactly 4 Odd Vertices (say \(A, B, C, D\))
When there are \(4\) odd vertices, they can be paired up in exactly \(3\) different ways:
• Pairing 1: \((AB)\) and \((CD)\) \(\implies \text{Total extra weight} = \text{Shortest}(AB) + \text{Shortest}(CD)\)
• Pairing 2: \((AC)\) and \((BD)\) \(\implies \text{Total extra weight} = \text{Shortest}(AC) + \text{Shortest}(BD)\)
• Pairing 3: \((AD)\) and \((BC)\) \(\implies \text{Total extra weight} = \text{Shortest}(AD) + \text{Shortest}(BC)\)
Steps to complete the problem:
1. Calculate the total extra weight for each of the \(3\) pairings.
2. Choose the pairing that gives the minimum sum.
3. The edges in this chosen pairing must be repeated.
4. \(\text{Optimal Route Length} = \text{Sum of all edges in graph} + \text{Minimum extra weight}\).
Key Takeaway: Always list every possible pairing explicitly in your working. State clearly which edges are repeated to secure full method marks.
---5. Quick Summary and Exam Revision Checklist
Before sitting your exam, check that you can confidently:
• Kruskal's Algorithm: Order all edges from smallest to largest, select lowest weights without creating cycles, stop at \(n - 1\) edges.
• Prim's Algorithm (Graphical): Grow a connected tree from a given node by adding the lowest-weight connected edge at each step.
• Prim's Algorithm (Matrix): Number columns, delete rows, select smallest value in numbered columns.
• Dijkstra's Algorithm: Methodically record working values, select the smallest non-permanent value, make it permanent, backtrack to find the route.
• Route Inspection: Identify odd-degree vertices, pair them up, find the combination with the smallest sum of shortest paths, add this extra distance to the total graph weight.