Algorithms on graphs

Welcome to Algorithms on Graphs!

In this chapter of Decision Mathematics 1, we move from the basic definitions of graph theory into the exciting world of algorithms. Algorithms are simply step-by-step instructions used to solve specific problems.
Why does this matter? Because every time you use a GPS for the fastest route home or a company tries to layout fiber-optic cables with the least amount of material, they are using these exact mathematical tools!
Don't worry if these seem like a lot of steps at first—think of them like a recipe. Follow the steps in order, and you'll get the right result every time.

1. Minimum Spanning Trees (MST)

Imagine you are connecting several houses to a water main. You want every house connected, but you want to use the minimum total length of pipe to save money. This is the Minimum Spanning Tree problem.

A Spanning Tree is a subgraph that includes every vertex of the original graph but has no cycles (it's "tree-like"). The Minimum Spanning Tree is the one where the sum of the weights of the edges is as small as possible.

Kruskal’s Algorithm

This is the "greedy" approach. You simply look for the cheapest edges available.

The Steps:
1. Sort all edges in the graph into ascending order of weight.
2. Select the edge with the least weight.
3. Select the next cheapest edge. Crucial Rule: If adding an edge creates a cycle, skip it!
4. Repeat until all vertices are connected (you will have \(n-1\) edges for \(n\) vertices).

Prim’s Algorithm (Graph Version)

Prim’s is different because it grows the tree from a starting point, like a plant growing roots.

The Steps:
1. Start at any vertex.
2. Look at all edges connecting the vertices you already have to vertices you don't have yet.
3. Choose the edge with the shortest weight.
4. Repeat until all vertices are included.

Prim’s Algorithm (Matrix Version)

In your exam, you are often asked to perform Prim's on a distance matrix. It looks scary, but it’s actually very mechanical!

The Steps:
1. Choose a starting vertex (usually A) and label it "1" above its column. Cross out row A.
2. Look at all the numbers in the columns that are labeled.
3. Circle the smallest available value in those columns (ignoring rows you've already crossed out).
4. The row of that circled value becomes your next vertex. Label its column with the next number (e.g., "2") and cross out its row.
5. Repeat until all columns are labeled.

Common Mistake: Forgetting to cross out the row of the vertex you just added. If you don't cross it out, you might accidentally pick an edge that leads back to a vertex you already have!

Key Takeaway: Kruskal's sorts all edges first; Prim's builds the tree one connected vertex at a time.

2. Finding the Shortest Path

This is the "Google Maps" section of the course. We want the shortest distance between a specific start and end point.

Dijkstra’s Algorithm

This algorithm finds the shortest path from a start vertex to all other vertices in the network.

The Steps:
1. Give the start node a permanent label of 0.
2. For every node connected to your current node, calculate a working value (Distance to current node + Edge weight).
3. If this new value is smaller than a previous working value, replace it.
4. Look at all the working values on the whole graph. Choose the smallest one—this becomes its permanent label.
5. Repeat from this new permanent node until the destination has a permanent label.

Memory Aid: Think of Dijkstra's as water flooding out from the start point. The permanent labels tell you exactly when the "water" first reached that point.

Floyd’s Algorithm

While Dijkstra starts from one point, Floyd’s finds the shortest path between every single pair of vertices in the graph. It uses two matrices: a Distance Matrix and a Route Matrix.

The Process:
For a graph with \(n\) vertices, you perform \(n\) iterations.
In iteration 1, you use vertex 1 as a "pivot." You check if going from \(A\) to \(B\) via vertex 1 is shorter than the current direct distance from \(A\) to \(B\).
If \(Dist(A, 1) + Dist(1, B) < Dist(A, B)\), you update the matrix with the new shorter distance.

Quick Review: Dijkstra is great for one-to-all; Floyd is for all-to-all.

3. The Route Inspection Algorithm

Also known as the Chinese Postman Problem. The goal is to travel along every edge at least once and return to the start, minimizing the total distance.

The Concept of "Odd Nodes":
A graph is Eulerian if all vertices have an even degree (number of edges). You can traverse it perfectly.
If a graph has odd nodes, you must repeat some edges. In the Edexcel syllabus, you will deal with networks having up to four odd nodes.

The Steps:
1. Identify all odd vertices.
2. List all possible pairings of these odd vertices.
3. Find the shortest path between each pair (using Dijkstra if necessary).
4. Choose the pairing with the minimum total weight.
5. Add these repeated edges to the total weight of the graph.

Did you know? If there are only two odd nodes, you just find the shortest path between them and repeat it. Simple!

4. The Traveling Salesman Problem (TSP)

The TSP is different from Route Inspection. Here, you want to visit every vertex once and return to the start, using the minimum distance. This is much harder to solve perfectly, so we find Bounds.

Upper Bounds (The "Good Enough" Route)

An Upper Bound is a distance we know we can achieve, even if it's not the absolute best.
1. Nearest Neighbour Algorithm: Start at a vertex, go to the nearest unvisited vertex. Repeat until all are visited, then return to start.
2. Double MST: Find the MST, double it (go out and back on every edge). This is always a valid tour, but usually quite long.

Lower Bounds (The "It Can't Be Better Than This" Value)

A Lower Bound is a theoretical minimum. You might not actually be able to achieve it.
The Deleted Vertex Method:
1. Remove one vertex and all its incident edges.
2. Find the Minimum Spanning Tree (MST) of the remaining vertices.
3. Add the weights of the two shortest edges that were connected to the deleted vertex.
4. The result is a lower bound. To find the best lower bound, repeat this for different deleted vertices and pick the highest value.

Key Takeaway: The actual optimal solution lies somewhere between your Highest Lower Bound and your Lowest Upper Bound.

Summary Checklist

- MST: Kruskal's (Edges) or Prim's (Nodes/Matrix).
- Shortest Path: Dijkstra's (One start) or Floyd's (All starts).
- Every Edge: Route Inspection (Pair the odd nodes).
- Every Vertex: TSP (Upper Bounds = Nearest Neighbour; Lower Bounds = Deleted Vertex + MST).

Don't worry if this seems tricky at first! The best way to learn algorithms is to grab a piece of paper, draw a small network, and physically follow the steps yourself. You've got this!