Algorithms on Graphs: Your Guide to Decision Making in Further Maths

Hello! Welcome to the exciting world of Decision Mathematics 1 (D1). This chapter, "Algorithms on Graphs," is perhaps the most practical and visual part of Further Maths. It’s all about finding the most efficient solutions—the cheapest connection, the quickest route, or the shortest delivery tour.

Don't worry if the term "algorithm" sounds complicated. An algorithm is simply a set of steps used to solve a specific problem. Think of it as a mathematical recipe! By the end of these notes, you’ll be able to solve real-world efficiency problems just like professional logistics managers and network engineers.

Section 1: The Basics of Networks (Graphs)

Before we run the algorithms, we need to understand the language of graphs.

What is a Graph?

A graph (or network) consists of points and lines connecting them.

  • Nodes (or Vertices): The points on the graph. (e.g., cities, junctions, computer servers).
  • Arcs (or Edges): The lines connecting the nodes. (e.g., roads, cables, flights).
  • Weights: A numerical value assigned to an arc, often representing distance, cost, time, or capacity.

Key Terminology

  • Path: A route that goes from one node to another, traveling along arcs.
  • Cycle (or Circuit): A path that starts and ends at the same node.
  • Degree (Order) of a node: The number of arcs attached to that node.
  • Connected Graph: A graph where every node can be reached from every other node.
  • Simple Graph: A graph with no loops (arcs starting and ending at the same node) and no multiple arcs between the same pair of nodes.
  • Directed Graph (Digraph): A graph where the arcs have arrows, meaning you can only travel in one direction (e.g., one-way streets).

Quick Review: Graphs are just diagrams of connections, and weights tell us how 'expensive' those connections are.

Section 2: Minimum Spanning Trees (MSTs)

Imagine you are connecting five office buildings with the cheapest possible fiber optic cable. You need to connect all buildings, but you don't want any unnecessary loops (cycles) of cable. This is where MSTs come in.

A Spanning Tree is a subgraph that connects all nodes without forming any cycles. The Minimum Spanning Tree (MST) is the spanning tree with the smallest total weight.

Algorithm 2.1: Kruskal’s Algorithm (The Cheapest-First Approach)

Kruskal's algorithm is greedy—it focuses on the cheapest arcs available at every step.

Goal: Build the tree by adding arcs in order of increasing weight, ensuring no cycles are created.

Step-by-Step Kruskal's
  1. List all the arcs in the network in order of increasing weight (from smallest to largest).
  2. Start with the smallest weight arc. Select it and add it to your tree.
  3. Look at the next smallest arc. Add it unless it creates a cycle with the arcs you have already selected.
  4. Repeat Step 3 until all nodes are connected.

Common Mistake Alert! The absolute rule for Kruskal’s is: DO NOT create a cycle! If adding an arc connects two nodes that are already connected by a path in your current partial tree, reject that arc.

Key Takeaway for Kruskal's: Start anywhere, work by weight order, and avoid loops.

Algorithm 2.2: Prim’s Algorithm (The Growing Tree Approach)

Prim’s algorithm is also greedy, but it focuses on growing the tree outwards from a starting point.

Goal: Start at one node and continuously connect the nearest unattached node.

Prim's Algorithm (Network Method - Visual)
  1. Start at any node (it doesn't matter which one, but often A is chosen). Mark it as 'in the tree'.
  2. Look at all the arcs connecting a node in the tree to a node outside the tree.
  3. Select the arc with the smallest weight among these choices.
  4. Add the selected arc and the new node it leads to into the tree.
  5. Repeat Steps 2-4 until all nodes are included in the tree.
Prim's Algorithm (Matrix Method)

This method is useful when the graph is given as a distance matrix.

  1. Start by selecting any row/column (e.g., A). Mark this column as 'included'.
  2. In the included rows/columns, find the smallest non-zero entry. This is the first arc.
  3. Circle the entry and cross out the corresponding row (it's now part of the tree).
  4. The new node just added dictates the next column you include.
  5. Repeat steps 2-4 until \(n-1\) arcs have been selected (where \(n\) is the number of nodes).

Analogy: If Kruskal is like a team of builders finding the cheapest individual roads anywhere in the country, Prim is like a single crew expanding their construction site outwards from their base.

Section 3: Shortest Path – Dijkstra’s Algorithm

The Minimum Spanning Tree connects everything cheaply. Dijkstra’s algorithm solves a different problem: finding the quickest, shortest, or cheapest route between two specific points (the start node and the end node).

Dijkstra's Algorithm works by systematically assigning and updating labels (distances) to nodes until the shortest path is guaranteed.

Key Concepts for Dijkstra's

  • Labeling: We assign labels \((d, p)\) to each node, where \(d\) is the distance from the start, and \(p\) is the immediate preceding node used to reach \(d\).
  • Temporary Labels: Labels that might change if a shorter route is found.
  • Permanent Labels: Labels that are finalized and confirmed as the absolute shortest distance to that node. Once a label is permanent, you never change it.
Step-by-Step Dijkstra’s Algorithm
  1. Start Node: Assign the start node a permanent label of \((0, -)\). All other nodes get temporary labels, usually \(( \infty, -)\) or just left blank initially.
  2. Scan (Develop) the Node: Choose the permanent labeled node with the smallest distance value (\(d\)). This is the node you are currently 'at'.
  3. Update Neighbors: Look at all temporary nodes connected to your current node. Calculate the potential new total distance (Old permanent distance + Arc weight).
  4. Relabel: If the new total distance is less than the node’s current temporary distance, update the label with the new distance and the current node as the predecessor.
  5. Make Permanent: Once you have scanned the current permanent node, look at all remaining temporary labels. Select the one with the smallest distance and make it permanent (circle the label).
  6. Repeat: Go back to Step 2, scanning the newly permanent node, until the destination node is made permanent.

Memory Aid: Always look for the smallest temporary label to make permanent next. This is crucial!

Common Mistake Alert! Students often forget to update temporary labels if a shorter route is found later in the process. Always compare the potential new route with the existing temporary label!

Key Takeaway for Dijkstra’s: Systematically confirm the shortest path to each node, one by one, moving outwards from the start.

Section 4: Route Inspection (The Chinese Postman Problem - CPP)

Imagine a postman or a salt gritting lorry that must travel along every single street exactly once and return to the depot, minimizing the total distance traveled.

The Chinese Postman Problem (CPP) requires finding the shortest closed trail that traverses every arc in a network.

The Rule of Even and Odd Nodes

If every node in the graph has an even degree (even number of arcs attached), the postman can complete the route without repeating any arcs. The route is simply the sum of all arc weights.

If there are nodes with an odd degree, the postman must repeat certain arcs to make the whole network traversable (Eulerian).

Step-by-Step CPP Solution
  1. Identify Odd Nodes: List all the nodes that have an odd degree. Since arcs always come in pairs, the number of odd nodes must always be even (2, 4, 6, etc.).
  2. Pair the Odd Nodes: We must pair up the odd nodes and find the shortest path between each pair. By doubling the arcs in these shortest paths, we effectively make the odd nodes 'even'.
  3. Calculate Shortest Pairings:
    • If there are 2 odd nodes (A and B), find the shortest path between A and B.
    • If there are 4 odd nodes (A, B, C, D), you must test all three possible pairings:
      (i) (A paired with B) AND (C paired with D)
      (ii) (A paired with C) AND (B paired with D)
      (iii) (A paired with D) AND (B paired with C)
    • Use Dijkstra’s algorithm or inspection to find the shortest path length for each pairing.
  4. Select the Minimum Pairing: Choose the pairing combination that results in the smallest total path length added.
  5. Calculate Total Route Length:
    Total Length = (Sum of all arc weights in the original network) + (Minimum added path length).
  6. State the Arcs to be Repeated: List the arcs that must be traversed twice.

Did you know? The algorithm is named after the Chinese mathematician Mei Ko Kwan, who developed it in 1962 while trying to find an optimal route for postal workers.

Key Takeaway for CPP: The challenge is turning the odd nodes into even nodes by adding the minimum possible extra distance.

Section 5: The Travelling Salesperson Problem (TSP)

The Travelling Salesperson Problem (TSP) asks: What is the shortest possible route that visits every node (city) exactly once and returns to the starting node?

The required route is a Hamiltonian Cycle of minimum weight.

Unlike the algorithms we’ve studied, there is NO simple, guaranteed algorithm to find the absolute minimum solution (the Optimal Tour) quickly. For a large number of nodes, finding the optimal solution is computationally too expensive.

Instead, we use approximation methods to find Upper Bounds (a tour we know is possible) and Lower Bounds (a distance we know the optimal tour must be greater than or equal to).

Approximation 5.1: Finding an Upper Bound

An Upper Bound is the length of any valid Hamiltonian Cycle (a tour visiting all nodes and returning to start). The easiest way to find a good upper bound is using the Nearest Neighbour Algorithm.

Nearest Neighbour Algorithm
  1. Start at a specified node (or try all nodes if not specified).
  2. From the current node, choose the arc leading to the nearest (unvisited) node.
  3. Repeat Step 2 until all nodes have been visited.
  4. Return directly to the start node to complete the tour.
  5. The total weight of this cycle is your Upper Bound.

Tour Adjustment: Sometimes, a minor adjustment (swapping two arcs) can lead to a shorter tour, providing a tighter (lower) Upper Bound.

Approximation 5.2: Finding a Lower Bound

A Lower Bound is the lowest possible cost we know the optimal tour must meet or exceed. We use the concept of a Minimum Spanning Tree (MST) or Deleted Node analysis to find this.

Lower Bound using the Minimum Spanning Tree (MST)

If you remove any node and its attached arcs from the network, the remaining graph will still need to be connected by a spanning tree. This is a common method for finding the Lower Bound.

  1. Choose any node (e.g., A) to 'delete' and remove all arcs connected to it.
  2. Find the Minimum Spanning Tree (MST) for the remaining nodes using Prim’s or Kruskal’s algorithm. Calculate its total weight.
  3. Identify the two shortest arcs that were originally connected to the deleted node (A).
  4. Calculate the Lower Bound:
    $$ \text{Lower Bound} = (\text{Weight of MST for remaining nodes}) + (\text{Weights of the two shortest arcs from A}) $$

The Logic: The optimal tour must leave A and return to A. It must use at least two arcs connected to A, and it must connect the rest of the nodes—the cheapest way to connect the rest is via an MST.

Key Takeaway for TSP: Since finding the exact answer is too hard, we create a window (Upper Bound to Lower Bound) where the optimal answer must lie.

Summary Checklist and Study Tips

Mastering the Algorithms
  • MST (Kruskal/Prim): Focus on connecting all nodes cheaply, avoiding cycles. Use Prim for matrices, Kruskal for quick visual sorting.
  • Shortest Path (Dijkstra): Be meticulous with temporary labels. Always make the smallest temporary label permanent next.
  • CPP: Identify odd nodes and calculate the minimum total weight required to pair them up.
  • TSP: Understand the difference between Upper Bound (a valid tour) and Lower Bound (theoretical minimum).

Encouraging Note: Decision Maths is procedural. Practice each algorithm step-by-step with small networks until the process becomes second nature. You’ve got this!