Welcome to Algorithms on Graphs II!
In your previous studies, you looked at how to find the shortest path between two points or how to connect all points with the minimum amount of cable. In this chapter, we are taking it to the next level. We are going to look at how to plan the most efficient routes for real-world scenarios—like a postman delivering letters to every house on a street or a salesperson visiting several cities.
These algorithms are the backbone of modern logistics, used by companies like Amazon and FedEx every single day. Don't worry if it seems a bit abstract at first; we will break it down step-by-step with simple analogies!
1. The Route Inspection Algorithm
Also known as the Chinese Postman Problem, this algorithm is all about finding the shortest route that travels along every edge (road) at least once and returns to the start.
The Core Concept: Even and Odd Nodes
Before we start, remember that the degree (or valency) of a node is the number of edges connected to it.
- An Even Node has an even number of edges (2, 4, 6...).
- An Odd Node has an odd number of edges (1, 3, 5...).
The Golden Rule: If every node in a network is even, you can travel every edge exactly once and return to the start. This is called an Eulerian circuit. The total distance is simply the sum of all weights in the network.
What if there are Odd Nodes?
If there are odd nodes, you must repeat some edges. Since we want the "shortest" route, we want to repeat the edges with the smallest possible total weight. In your exam, you will usually deal with networks having either two or four odd nodes.
Step-by-Step: The Inspection Process
- Find all nodes with an odd degree.
- List all possible pairings of these odd nodes.
- For each pairing, find the shortest path between the nodes.
- Choose the pairing with the minimum total weight.
- Add this minimum weight to the total weight of all edges in the network. This is your final answer!
Example for 4 Odd Nodes (A, B, C, D):
There are only three ways to pair them:
1. (AB and CD)
2. (AC and BD)
3. (AD and BC)
Tip: Just pick one node (like A) and pair it with every other node. The remaining two nodes form the second pair automatically!
Quick Review Box:
- Eulerian: All nodes even.
- Semi-Eulerian: Two nodes odd (you'd start at one and end at the other).
- Route Inspection: Repeat edges between odd nodes to make the route "effectively" even.
2. The Travelling Salesman Problem (TSP)
While the Postman wants to visit every edge, the Travelling Salesman wants to visit every vertex (node) exactly once and return to the start. This is much harder to solve!
Two Types of TSP
- Classical TSP: You must visit each vertex exactly once and cannot revisit any. This usually applies to complete graphs.
- Practical TSP: You can revisit vertices if it makes the total trip shorter. We turn a "Practical" problem into a "Classical" one by using a table of least distances.
The Triangle Inequality
This is a fancy way of saying "the direct route is the shortest." Formally:
\( \text{Length } AB \leq \text{Length } AC + \text{Length } CB \)
If this is true for all nodes, the shortest path between two points is always the direct edge between them.
3. Finding an Upper Bound
Because the TSP is so hard, we often look for a Upper Bound—a "good enough" route that we know we can definitely achieve. We use two main methods.
Method A: Nearest Neighbour Algorithm
This is a "greedy" algorithm. It’s like being a lazy shopper who always goes to the closest shop next.
- Choose a starting node.
- Go to the nearest unvisited node.
- Repeat until all nodes are visited.
- Crucial Step: You must return to the start node at the end!
Mistake to Avoid: Students often forget the very last step—adding the distance from the last node back to the first one.
Method B: Minimum Spanning Tree (MST) x 2
1. Find the MST of the whole network (using Prim’s or Kruskal’s).
2. Double the weight of the MST. This is an initial upper bound.
3. Look for shortcuts to reduce this weight (using the table of least distances) to find a better upper bound.
Did you know? The "Upper Bound" is the maximum we want to pay for the trip. We are always looking for ways to push this number lower!
4. Finding a Lower Bound
A Lower Bound is a value that our best possible route cannot be shorter than. It tells us: "You definitely can't do the whole trip in less than this amount of time/distance."
The Deleted Vertex Method
- Delete one vertex and all the edges connected to it.
- Find the Minimum Spanning Tree (MST) of the remaining nodes.
- Find the two shortest edges that were connected to the deleted vertex.
- Lower Bound = (Weight of MST) + (Sum of two shortest edges).
Don't worry if this seems tricky! Just remember: a Lower Bound doesn't have to be a valid route (it often looks like a "Y" shape rather than a circle). Its job is just to provide a floor for our expectations.
Summary Takeaway:
- Upper Bound: A route we can do (usually found by Nearest Neighbour).
- Lower Bound: A value we can't beat (found by deleting a vertex).
- The Optimal Solution lies somewhere between the two!
5. Final Summary and Common Pitfalls
Key Terms Review:
- Walk: A sequence of edges.
- Tour: A walk that visits every vertex and returns to the start.
- Shortcuts: Used in TSP to skip vertices we've already seen, improving our Upper Bound.
Common Mistakes to Avoid:
- In Route Inspection: Forgetting to add the "extra" repeated edges to the original total weight of the graph.
- In Nearest Neighbour: Forgetting to add the final edge back to the starting vertex.
- In Lower Bounds: Choosing the two shortest edges from the entire graph instead of the two shortest edges connected specifically to the deleted vertex.
Keep practicing these steps! Decision Mathematics is all about following the "recipe" (the algorithm) perfectly. You've got this!