Welcome to Algorithms on Graphs II!
In your previous studies, you learned how to find the shortest path between two specific points (Dijkstra's Algorithm). But what if you are a postman who needs to walk down every single street in a neighborhood? Or a delivery driver who needs to visit every house and return home?
In this chapter, we explore two of the most famous problems in Decision Mathematics: the Route Inspection Problem and the Travelling Salesman Problem. These algorithms help businesses save millions of dollars in fuel and time every year!
1. The Route Inspection Problem
Also known as the Chinese Postman Problem, the goal here is to find the shortest possible route that travels along every edge of a network at least once and returns to the starting vertex.
The Logic Behind It
Imagine a graph where every vertex has an even degree (an even number of edges meeting there). This is called an Eulerian graph. In these graphs, you can travel every edge exactly once and end up back where you started. Life is easy!
However, most real-world maps have odd nodes (vertices where an odd number of edges meet). To finish your route, you must repeat some edges.
Step-by-Step Algorithm (for up to 4 odd nodes)
- Find the odd nodes: Look at every vertex and count how many edges connect to it. List the ones with an odd count.
- Identify the pairings: If you have two odd nodes (A and B), there is only one pairing: AB. If you have four odd nodes (A, B, C, D), there are three possible pairings:
- AB and CD
- AC and BD
- AD and BC
- Find the shortest paths: Calculate the shortest distance between the nodes in each pair.
- Select the minimum: Choose the pairing with the lowest total weight.
- Calculate the final route: The total length = (Sum of all edges in the network) + (Weight of the shortest pairing).
Quick Tip: Don't worry if this seems tricky at first! Just remember: Odd nodes are the problem. We "fix" them by repeating the shortest paths between them until they effectively become even.
Common Mistake: Forgetting to add the weight of the repeated edges to the total sum of all edges in the graph. Always double-check your addition!
Key Takeaway: The Route Inspection Problem is about visiting every edge. To minimize the distance, we repeat the shortest possible paths between pairs of odd nodes.
2. The Travelling Salesman Problem (TSP)
Unlike the postman who wants to walk every street, the Travelling Salesman only cares about visiting every vertex (city/house) and returning to the start, using the shortest route possible.
Classical vs. Practical TSP
- Classical TSP: Every vertex is directly connected to every other vertex (a complete graph), and the distances satisfy the triangle inequality (the direct path is always the shortest).
- Practical TSP: Not all nodes are directly connected. To solve this, we first turn it into a complete graph by finding the shortest "distanced" paths between every pair of nodes.
Did you know? The TSP is a "Hard" problem in computer science. As the number of cities increases, the number of possible routes grows so fast that even the world's most powerful computers can't find the perfect answer quickly!
3. Finding Upper and Lower Bounds
Because finding the exact shortest route for TSP is so hard, we instead find a "window" where the answer must lie. This window is defined by a Lower Bound and an Upper Bound.
The Upper Bound (The "Good Enough" Route)
An upper bound is a distance we know we can achieve. It might not be the best, but it's a valid route. We often use the Nearest Neighbour Algorithm:
- Choose a starting vertex.
- Go to the closest unvisited vertex.
- Repeat until all vertices are visited.
- Return to the start.
Note: You can also improve an upper bound by using "Short Cuts" on a doubled Minimum Spanning Tree.
The Lower Bound (The "Best Case" Scenario)
A lower bound is a value that the optimal route cannot be shorter than. We use the MST Method:
- Remove a node: Pick a vertex (e.g., node A) and temporarily delete it and all edges connected to it.
- Find the MST: Find the Minimum Spanning Tree for the remaining nodes (using Prim's or Kruskal's).
- Reconnect: Add the weights of the two shortest edges that were connected to the deleted node A.
- Total: Lower Bound = (Weight of MST) + (Two shortest edges from node A).
Analogy: Think of the Lower Bound like the floor of a room and the Upper Bound like the ceiling. The actual best route is somewhere in between!
Quick Review Box:
- Nearest Neighbour gives an Upper Bound.
- Deleting a node + MST + 2 shortest edges gives a Lower Bound.
4. Converting to a Complete Network
Sometimes, a question will give you a network that isn't "complete" (some cities aren't directly linked). To apply TSP algorithms, you must first create a table of shortest distances.
This means if you want to go from A to C, but there is no direct edge, you might find that going A → B → C is the shortest way. You then treat the distance of A → C as the total of those two steps.
Key Takeaway: For TSP, we are looking for a Hamiltonian Cycle (visit every vertex once and return). We use bounds to narrow down the possible minimum distance.
Summary Checklist
✓ Route Inspection: Did I find all odd nodes and the cheapest pairings?
✓ Nearest Neighbour: Did I always pick the closest unvisited node?
✓ Lower Bound: Did I remember to add the two shortest edges back to the MST?
✓ Accuracy: Did I read the table/matrix correctly? (A very common source of lost marks!)
You've got this! Decision Mathematics is all about following the steps carefully. Keep practicing the pairings and the MST method, and you'll be a pro in no time.