Algorithms on Graphs: Decision & Discrete Mathematics
Welcome to Algorithms on Graphs! Whether you use Google Maps to find the quickest route home, or wonder how delivery companies plan their courier routes across Northern Ireland, graph algorithms are at work behind the scenes. In this chapter from A2 Section D: Discrete and Decision Mathematics, you will learn standard step-by-step methods (algorithms) to solve network problems efficiently. Don't worry if this seems tricky or abstract at first — graph algorithms are simply structured recipes that guarantee the right answer when followed step by step.
1. Quick Refresh: Essential Graph Terminology
Before diving into the algorithms, let's review the fundamental vocabulary:
• Vertex (or Node): A point in a network, usually representing a location or state (plural: vertices).
• Edge (or Arc): A line connecting two vertices, representing a road, cable, or relationship.
• Weight: A numerical value assigned to an edge, such as distance, travel time, or financial cost.
• Degree (or Valency): The number of edges connected to a vertex.
• Path: A sequence of connected edges where no vertex is visited more than once.
• Cycle: A closed path that starts and finishes at the exact same vertex without repeating any other vertices.
• Tree: A connected graph that contains no cycles.
• Spanning Tree: A tree that connects all vertices of a graph together. If a graph has \(n\) vertices, any spanning tree will have exactly \(n - 1\) edges.
Quick Memory Aid: "Trees have no loops!" If you have \(n\) nodes, a tree always uses exactly \(n - 1\) edges. If you add one more edge to a spanning tree, you inevitably create a cycle.
2. Minimum Spanning Trees (MST)
Imagine you are tasked with laying fibre-optic broadband cable between towns. You want every town connected to the network, but broadband cable is expensive, so you want the total length of cable to be as small as possible. This is the Minimum Spanning Tree (MST) problem.
Kruskal's Algorithm
Kruskal's algorithm is an edge-based greedy algorithm. You focus on picking the shortest available edges across the whole graph, regardless of where they are, as long as they don't form a cycle.
Step-by-step Process:
Step 1: List all edges in the graph in ascending order of weight (smallest to largest).
Step 2: Select the edge with the lowest weight.
Step 3: Look at the next shortest edge in your list. If adding it creates a cycle with previously chosen edges, reject it. Otherwise, select it.
Step 4: Repeat Step 3 until you have selected exactly \(n - 1\) edges (where \(n\) is the total number of vertices).
Step 5: Calculate the total weight by summing the weights of all selected edges.
Common Mistake to Avoid: Forgetting to state which edges were rejected and why. In CCEA exams, you must explicitly list the edges you consider and note: "Reject edge XY as it creates cycle XY..." to earn full method marks.
Prim's Algorithm
Prim's algorithm is a vertex-based (or tree-growing) greedy algorithm. Instead of jumping around the graph, you start at one vertex and grow a single connected cluster outwards by choosing the shortest edge that connects a vertex inside the cluster to a vertex outside it.
Step-by-step Process (Graphical Form):
Step 1: Choose an initial starting vertex (specified by the question).
Step 2: Look at all edges connecting vertices already in your tree to vertices not yet in your tree.
Step 3: Choose the edge with the minimum weight. Add this edge and its new vertex to your tree.
Step 4: Repeat until all \(n\) vertices are included (meaning you have chosen \(n - 1\) edges).
Step-by-step Process (Matrix / Distance Table Form):
In exam papers, Prim's algorithm is frequently presented as a distance matrix:
Step 1: Choose a start vertex. Cross out the row corresponding to this start vertex and label its column with the number 1.
Step 2: Look down all numbered columns for the smallest uncrossed value.
Step 3: Circle this smallest value, note the edge it represents, cross out that row, and label that new column with the next consecutive number (2, 3, etc.).
Step 4: Repeat until all rows are crossed out and all columns are numbered.
Key Takeaway for MST:
• Kruskal's selects the shortest overall edges and prevents cycles.
• Prim's grows a single connected tree outward from a starting vertex.
• Both algorithms will always produce an MST with the same total minimum weight.
3. Dijkstra's Shortest Path Algorithm
Dijkstra's algorithm finds the shortest path from a single starting vertex (source) to every other vertex in a weighted network with non-negative edge weights.
Understanding the Vertex Box
At each vertex \(V\), you will fill in a standard box containing three pieces of information:
1. Vertex Name / Label
2. Order of Labelling (Permanent Sequence Number): Indicates when the vertex became permanently fixed.
3. Final (Permanent) Distance: The true minimum distance from the start vertex to this vertex.
4. Working Values: Temporary tentative distances calculated while exploring paths.
Step-by-step Algorithm:
Step 1: Initialise
Set the start vertex with a permanent value of \(0\) and an order of labelling of 1.
Step 2: Update Working Values
From the vertex \(U\) most recently made permanent, look at all directly connected neighbours that do not yet have permanent labels. Calculate:
\( \text{New Working Value} = \text{Permanent Value of } U + \text{Edge Weight to Neighbour} \)
If this new value is strictly smaller than the neighbour's existing working value (or if the neighbour has no working value yet), write this new value down in the working values section.
Step 3: Select the Next Permanent Vertex
Scan all non-permanent vertices across the entire graph. Identify the one with the smallest working value. Make this working value its permanent label, and assign the next sequential order number.
Step 4: Repeat
Repeat Steps 2 and 3 until the destination vertex (or all vertices) has received a permanent label.
Step 5: Traceback to Find the Path
To find the actual route from start \(S\) to destination \(T\):
Start at destination \(T\) and work backwards. An edge connecting vertex \(A\) to vertex \(B\) is on the shortest path if:
\( \text{Permanent Value}(B) - \text{Weight of Edge } AB = \text{Permanent Value}(A) \)
Trace backwards until you reach the start vertex \(S\), then write the route forwards.
Common Mistake to Avoid: When choosing the next permanent label, only choose from the smallest current working values across the entire graph, not just neighbours of the vertex you just labelled!
Key Takeaway for Dijkstra: Working values are temporary estimates; once a vertex gets a permanent label, its shortest distance from the start is locked in and will never change.
4. Route Inspection Problem (Chinese Postman Problem)
Imagine a postman delivering mail along every road in a village before returning to the sorting office. The goal is to traverse every edge at least once while minimising the total distance walked.
Eulerian & Semi-Eulerian Graphs
• Eulerian Graph: A connected graph where every single vertex has an even degree. You can traverse every edge exactly once and return to the start without repeating any edge.
• Semi-Eulerian Graph: A connected graph with exactly two vertices of odd degree. You can traverse every edge once, starting at one odd vertex and finishing at the other.
• Handshaking Lemma: The sum of degrees in any graph is equal to \(2 \times \text{Number of Edges}\). Consequently, the number of odd-degree vertices in any graph is always even (e.g., 0, 2, 4, 6...).
Solving the Route Inspection Problem
Case 1: All vertices are even (Eulerian graph)
The optimal route length is simply the sum of all edge weights in the graph.
Case 2: There are exactly two odd vertices (\(A\) and \(B\))
You must repeat the shortest path between \(A\) and \(B\).
\( \text{Minimum Total Length} = \text{Sum of all edge weights} + \text{Shortest distance between } A \text{ and } B \)
Case 3: There are four odd vertices (\(A, B, C, D\))
Four odd vertices can be paired in three distinct ways:
1. Pair \((AB)\) and \((CD)\): Total added weight = \(\text{dist}(AB) + \text{dist}(CD)\)
2. Pair \((AC)\) and \((BD)\): Total added weight = \(\text{dist}(AC) + \text{dist}(BD)\)
3. Pair \((AD)\) and \((BC)\): Total added weight = \(\text{dist}(AD) + \text{dist}(BC)\)
Step-by-step Method for Four Odd Vertices:
Step 1: Calculate the sum of all edge weights in the network.
Step 2: Find the valency (degree) of each vertex and identify all odd vertices.
Step 3: Write down all possible pairings of the odd vertices.
Step 4: Find the shortest path between each pair (check paths carefully — sometimes the shortest path goes via another vertex!).
Step 5: Choose the pairing combination that gives the minimum total added weight.
Step 6: Compute: \( \text{Total Route Length} = \text{Sum of All Edges} + \text{Minimum Added Weight} \).
Key Takeaway for Route Inspection: We want to cover every edge. Odd valencies force us to backtrack; by pairing them up with the shortest possible paths, we minimise the extra distance.
5. The Travelling Salesperson Problem (TSP)
While the Route Inspection Problem focuses on visiting every edge, the Travelling Salesperson Problem (TSP) focuses on visiting every vertex exactly once and returning to the start vertex with the minimum total cost. A closed cycle visiting every vertex once is called a Hamiltonian cycle.
Classical vs Practical TSP
• Classical TSP: Every vertex must be visited exactly once before returning to the start.
• Practical TSP: Each vertex must be visited at least once. In this case, you can revisit a vertex if doing so creates a shorter shortcut (this assumes the triangle inequality holds: \( \text{dist}(AC) \le \text{dist}(AB) + \text{dist}(BC) \)).
Finding the exact optimal tour in a large graph is extremely difficult (it is an NP-hard problem). Therefore, we calculate Upper Bounds and Lower Bounds to narrow down the possible minimum tour length:
\( \text{Lower Bound} \le \text{Optimal Tour Length} \le \text{Upper Bound} \)
Finding an Upper Bound: Nearest Neighbour Algorithm
An upper bound represents a guaranteed achievable tour length. Any real cycle you find gives an upper bound.
Step-by-step Nearest Neighbour Algorithm:
Step 1: Select a starting vertex specified by the problem.
Step 2: Move to the nearest unvisited vertex (the one connected with the smallest edge weight).
Step 3: Repeat Step 2 until all vertices have been visited.
Step 4: Add the weight of the edge that returns from the last visited vertex directly back to the starting vertex.
Step 5: The sum of these edges is your Upper Bound.
Note: If you repeat Nearest Neighbour from different starting vertices, the lowest value obtained gives the best (tightest) upper bound.
Finding a Lower Bound: Residual Minimum Spanning Tree Method
A lower bound gives a value that the true optimal tour cannot fall below. It is often not a valid tour itself, but a theoretical floor.
Step-by-step Lower Bound Method:
Step 1: Choose a vertex \(V\) to temporarily delete from the graph, along with all edges connected to it.
Step 2: Find the Minimum Spanning Tree (MST) of the remaining subgraph using Prim's or Kruskal's algorithm.
Step 3: Find the two shortest edges that connected the deleted vertex \(V\) back to the rest of the graph.
Step 4: Add the weights together:
\( \text{Lower Bound} = \text{Weight of MST of remaining vertices} + \text{Sum of 2 shortest edges incident to } V \)
Note: If you calculate lower bounds by deleting different vertices, the highest value obtained gives the best (tightest) lower bound.
Summary Comparison: Route Inspection vs TSP
• Route Inspection (Chinese Postman): Covers every edge at least once. Based on Eulerian graphs and vertex valencies.
• Travelling Salesperson (TSP): Visits every vertex and returns to start. Based on Hamiltonian cycles, bounded by Nearest Neighbour (Upper Bound) and Deleted Vertex MST (Lower Bound).
Quick Revision Checklist
Before sitting your exam, make sure you can confidently:
• Execute Kruskal's algorithm by listing edges and explicitly stating rejected cycles.
• Execute Prim's algorithm on both network diagrams and distance matrices.
• Complete a full Dijkstra table/diagram with working values, permanent labels, and correct traceback paths.
• Identify odd vertices, list all pairings, and solve the Route Inspection Problem.
• Calculate an Upper Bound for TSP using the Nearest Neighbour Algorithm.
• Calculate a Lower Bound for TSP using the vertex deletion and residual MST method.