Welcome to Algorithms on Graphs II!

In your previous studies, you learned how to find the shortest path between two specific points (Dijkstra's) and how to connect all points with the minimum amount of "cable" (Prim's and Kruskal's). Now, we are taking it a step further. We’re going to look at how to navigate entire networks efficiently.

Whether it’s a postman delivering mail to every house on every street or a delivery driver visiting several different cities in one day, these algorithms help us find the most cost-effective and time-saving routes. Don't worry if it seems like a lot of steps at first—once you see the patterns, it becomes a very logical "puzzle" to solve!

1. The Route Inspection Algorithm (Chinese Postman Problem)

The goal here is simple: travel along every single edge in a network at least once and return to your starting point, while keeping the total distance as short as possible.

Understanding Node Degrees

Before we start, remember the "handshaking" rule: A node is odd if it has an odd number of edges connected to it, and even if it has an even number. For a route to traverse every edge once and return to the start without repeating any edges (an Eulerian circuit), all nodes must be even.

The Process

If a network has odd nodes, we must repeat some edges. The algorithm finds which edges to repeat to add the minimum possible extra distance.

  1. Identify all odd nodes in the network.
  2. List all possible pairings of these odd nodes.
  3. For each pairing, find the shortest path between the nodes.
  4. Choose the pairing with the lowest total distance.
  5. Add this minimum distance to the sum of all edges in the original network.
Quick Review: The Pairings Rule

In D1, you will deal with networks having up to four odd nodes. If you have four odd nodes (let’s call them A, B, C, and D), there are exactly three ways to pair them:
1. (AB) and (CD)
2. (AC) and (BD)
3. (AD) and (BC)

Common Mistake: Students often forget to check the shortest path between nodes. Sometimes the shortest way from A to B isn't a direct edge; it might be going through another node!

Key Takeaway: The Route Inspection total = (Sum of all edges) + (Minimum extra distance from pairings).

2. The Travelling Salesman Problem (TSP)

While the Route Inspection problem focuses on edges, the TSP focuses on vertices. The goal is to visit every vertex exactly once and return to the start.

Practical vs. Classical TSP

Classical TSP: You visit each vertex exactly once. This usually happens in a "complete" graph where every node is directly connected to every other node.
Practical TSP: You must visit each vertex, but you are allowed to pass through a vertex more than once if it makes the trip shorter. In these cases, we often convert the network into a complete network of shortest distances first.

The Triangle Inequality

This sounds fancy, but it's simple! It states that the direct path between two points is never longer than a path that goes through a third point.
Formally: \( d(A, C) \le d(A, B) + d(B, C) \).
If a network satisfies this, "short-cuts" will always save you distance.

Did you know? The TSP is "NP-hard," which is a computer science way of saying it's incredibly difficult for computers to find the absolute perfect answer for large networks. That’s why we use Bounds.

3. Finding an Upper Bound

An Upper Bound is a "guaranteed" distance. We know the best possible route is this distance or less.

Method A: The Nearest Neighbour Algorithm

This is a "greedy" algorithm—you always pick the closest unvisited city next.

  1. Start at a given vertex.
  2. Go to the nearest unvisited vertex.
  3. Repeat until all vertices are visited.
  4. Return to the starting vertex.

Note: The Upper Bound can change depending on which vertex you start at. Usually, the exam will tell you where to begin!

Method B: Doubling the MST

  1. Find the Minimum Spanning Tree (MST) using Prim's or Kruskal's.
  2. Double the weight of the MST (this represents walking every path in the tree twice to get back to the start).
  3. Apply short-cuts to avoid visiting nodes twice, using the shortest available routes to keep the distance down.
Quick Review Box

Upper Bound Checklist:
- Did I visit every node?
- Did I return to the start?
- Is my calculation correct? (Double-check your addition!)

4. Finding a Lower Bound

A Lower Bound is a value that the optimal route is guaranteed to be at least as long as. The real answer is this distance or more.

The Deleted Vertex Method

  1. Delete one vertex and all the edges connected to it.
  2. Find the MST of the remaining vertices.
  3. Find the two shortest edges that were connected to the deleted vertex.
  4. Lower Bound = (Weight of MST) + (Sum of those two shortest edges).

Encouragement: If you calculate different lower bounds by deleting different vertices, the highest value is the "best" lower bound because it's the most accurate restriction.

Key Takeaway: We combine these to create an interval for the optimal solution:
Lower Bound \(\le\) Optimal Solution \(\le\) Upper Bound

Chapter Summary & Tips

  • Route Inspection: Think edges. Focus on pairing up odd nodes.
  • TSP: Think vertices. Focus on Upper and Lower bounds.
  • Memory Aid: "Nearest Neighbour" is a greedy friend who wants the closest snack (Upper Bound). "Deleted Vertex" is a builder who needs a foundation (MST) and two supports (two shortest edges) (Lower Bound).
  • In the Exam: Always show your pairings clearly for Route Inspection. For TSP, if you are given a table, make sure you are looking for the smallest numbers that haven't been "crossed out" yet.

You've got this! Practice identifying whether a question is asking for Route Inspection (all roads) or TSP (all towns), and the rest is just following the steps.