Welcome to Algorithms on Graphs II!

In our previous chapter, we looked at finding the shortest path between two specific points (Dijkstra's Algorithm). In this chapter, we are moving from being "tourists" trying to get from A to B, to being "delivery drivers" or "postmen."

We are going to learn the Route Inspection Algorithm, also famously known as the Chinese Postman Problem. The goal here isn't just to reach a destination; it’s to travel along every single edge in a network at least once and return to where we started, all while keeping the total distance as short as possible.

Prerequisite Refresh: The Basics of Nodes

Before we dive in, let’s quickly remind ourselves of two key terms from earlier in the course:

  • Degree (or Valency): The number of edges connected to a node.
  • Odd and Even Nodes: If a node has an even number of edges connected to it, it’s an even node. If it has an odd number, it’s an odd node.

Quick Tip: In any graph, the number of odd nodes is always even (e.g., you can have 0, 2, or 4 odd nodes, but never 3).

The Core Concept: Eulerian Graphs

The "perfect" scenario for a postman is an Eulerian Graph. This is a network where every single node is even.

If all nodes are even, you can start at any vertex, travel every edge exactly once, and end up back at the start without ever repeating a road. In this case, your total distance is simply the sum of all weights in the network.

Analogy: Think of it like drawing a shape without lifting your pen or tracing over the same line twice.

What if the Graph Isn't Perfect?

In the real world, most networks have odd nodes. If a graph has odd nodes, you must repeat some edges to get back to the start. The Route Inspection Algorithm helps us decide which edges to repeat to minimize the extra distance.

Scenario 1: Two Odd Nodes

If there are exactly two odd nodes, the graph is "Semi-Eulerian." To complete the route and return to the start, you must repeat the shortest path between these two odd nodes.

Step-by-Step for 2 Odd Nodes:
1. Find the two nodes with odd degrees.
2. Find the shortest path between them (you can usually do this by "inspection"—just looking at the graph).
3. Add the weight of this shortest path to the total sum of all edges in the network.

Scenario 2: Four Odd Nodes

This is the most complex version you will face in the 8FM0 syllabus. If there are four odd nodes, you must pair them up and repeat the shortest paths between the pairs. There are always three possible pairings.

Step-by-Step for 4 Odd Nodes:
Suppose your odd nodes are \(A, B, C,\) and \(D\).
1. List the three possible ways to pair them up:
   • Pair 1: \((AB)\) and \((CD)\)
   • Pair 2: \((AC)\) and \((BD)\)
   • Pair 3: \((AD)\) and \((BC)\)
2. Calculate the shortest distance for each pairing by adding the weights of the two paths together.
3. Choose the pairing with the smallest total.
4. Add this "extra" distance to the total sum of all edges in the network.

Did you know? This algorithm is called the "Chinese Postman Problem" because it was first studied by the Chinese mathematician Mei-Ko Kwan in 1960!

Example Walkthrough

Imagine a small network with a total edge weight of 150km. You find four odd nodes: A, B, C, and D.

Shortest distances between them are: \(AB = 10, AC = 12, AD = 15, BC = 14, BD = 11, CD = 13\).

Let's check the pairings:
1. \((AB + CD) = 10 + 13 = 23\)
2. \((AC + BD) = 12 + 11 = 23\)
3. \((AD + BC) = 15 + 14 = 29\)

Both Pairing 1 and Pairing 2 give the minimum extra distance of 23.
Final Answer: Total Route = \(150 + 23 = 173\text{km}\).

Common Mistakes to Avoid

  • Forgetting the "Total Sum": Students often find the extra distance (e.g., 23) but forget to add it to the sum of all the original edges in the graph.
  • Missing an Odd Node: Always double-check the degree of every node. If you miss one, your pairings will be wrong!
  • Not checking all 3 pairings: Don't just pick the first two odd nodes you see. You must check all three combinations for 4 nodes.

Don't worry if this seems tricky at first! Just remember that odd nodes are the "problem areas." We are just trying to find the cheapest way to "fix" those problems by doubling up the roads between them.

Summary: Key Takeaways

The Goal: Travel every edge at least once and return to the start.

Quick Review Box:
• 0 Odd Nodes: Total distance = Sum of all edges.
• 2 Odd Nodes: Total distance = Sum of all edges + Shortest path between the 2 odd nodes.
• 4 Odd Nodes: Total distance = Sum of all edges + Smallest total of the 3 possible pairings of the 4 odd nodes.

What's Next?

Now that you can find the length of the route, practice listing the actual route (the sequence of nodes). Remember, if you "repeated" an edge like \(AB\), your final path must literally pass through \(A\) and \(B\) twice!