117 – The Postal Worker Rings Once

Problem: Given a sequence of streets (connecting given intersections), write a program that determines the minimal cost tour that traverses every street at least once. The tour must begin and end at the same intersection.

The input is a set of edges and their corresponding weights (costs). There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection. Also, you can assume that the graph is a simple (no multiedges) connected graph. [Source]

Category: graph theory, Eulerian path, shortest paths

Discussion: Pretty simple if you know basic graph theory. A nice problem, though. The problem specifies that there are at most two intersections with odd degree. Now, a connected graph cannot have an odd number of vertices with odd degree. This follows from the Handshaking Lemma which states that the total degree in a graph is even. As a result, there cannot be a single intersection with odd degree. Only two cases arise:

  1. There are no nodes with odd degree. If all nodes in a graph have an even degree, the graph has an Eulerian circuit. So, the minimal cost tour is simply the sum of all edge weights.
  2. There are two nodes with odd degree. This implies the existence of an Eulerian path that starts at one of the odd degree nodes and ends at the other odd degree node. Since we need to return to the starting point, we need to consider the cost of the return path from end to start along with the cost of the Eulerian path. Thus, the problem now reduces to finding the shortest path between the two odd degree nodes! Thus, cost(minimal tour) = cost(Eulerian path from ‘start’ to ‘end’) + cost(shortest path between ‘start’ and ‘end’)

You can draw a few graphs to realise that this is true. It can be proved as well.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: