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:
- 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.
- 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.
First Principles 