D1.3 - Algorithms on graphs II

A route-inspection, or Chinese postman, problem asks for the shortest closed walk that traverses every edge of a connected weighted network at least once and returns to its start. First add every edge weight to obtain the unavoidable base total $S$; extra distance comes only from edges that must be repeated.

A closed walk enters and leaves each vertex in pairs, so every vertex must have even degree after repeated edges are included. If the network already has no odd vertices, an Eulerian closed walk exists and the minimum length is $S$. Odd vertices always occur in an even number.

When there are two odd vertices, duplicate a shortest path between them. With four odd vertices $A,B,C,D$, inspect all three pairings: $AB+CD$, $AC+BD$ and $AD+BC$, using shortest-path distances rather than necessarily direct edges. Choose the pairing with the least total, duplicate the edges on those paths, then trace a closed walk using every original edge and every required repeat.

Suppose $S=120$ and the shortest-path pairing totals for four odd vertices are 13, 18 and 15. Duplicate the paths belonging to the total 13, so the minimum route length is $120+13=133$. The written route must show those repeated edges and finish where it started.

If a question explicitly allows different start and finish vertices, those two vertices may remain odd; make every other vertex even with the least additional shortest paths. This is a stated-endpoints extension: the core D1.3.1 task is the closed route that returns to its start.

A travelling-salesperson problem (TSP) seeks a minimum-length tour that visits every required vertex and returns to its start. A tour is a closed walk; unlike route inspection, the goal is to visit vertices, not to traverse every edge.

The triangle inequality says that a direct classical edge from $A$ to $C$ is no longer than travelling from $A$ to $C$ through another vertex $B$: $w(A,C)\leq w(A,B)+w(B,C)$. This is why a repeated intermediate vertex in a closed walk can be shortcut without increasing its length.

To improve an upper bound, identify a repeated vertex in the walk and replace the surrounding detour by the corresponding direct edge in the complete graph, while still visiting every required vertex and returning to the start. Continue only while the result remains a valid tour. In a practical network, a classical edge represents the shortest route between its endpoints and must later be expanded back into real network edges.

If a closed walk contains $A-B-C-B-D-A$, then $B$ is revisited. In its complete metric graph, the section $C-B-D$ may be replaced by $C-D$. The resulting tour $A-B-C-D-A$ is no longer than the original walk and is therefore at least as good an upper bound.

For a classical TSP, a lower bound is a value the optimal tour cannot be below, while an upper bound is the length of an actual valid tour. Minimum spanning tree (MST) methods produce both kinds of information without claiming the exact optimum.

For a lower bound, delete one vertex $v$ and all its incident edges. Find an MST on the remaining vertices, then add the two least edge weights incident to $v$ in the complete graph. Every tour must connect $v$ twice, and removing $v$ from a tour leaves a connected spanning structure, so its length cannot be less than this total. Trying different deleted vertices can give different lower bounds; retain the largest valid one.

For an MST upper bound, double every MST edge to form a closed walk that reaches every vertex. Its length is twice the MST weight. Shortcut repeated vertices using the triangle inequality until a tour remains; the resulting tour length $U$ is an upper bound and may be smaller than the doubled-tree length.

For a practical network, first form a complete network or table whose entry for each vertex pair is their shortest-path distance in the original network. Apply the classical bound methods to that complete network. When reporting a practical route, expand each selected complete-network edge back to its corresponding shortest path.

If deleting $A$ leaves an MST of weight 22 and the two least edges incident to $A$ have weights 5 and 7, then $L_A=22+5+7=34$. If doubling and shortcutting an MST gives a valid tour of length 38, then the optimum $T$ satisfies $34\leq T\leq38$.

The nearest-neighbour algorithm constructs a travelling-salesperson tour from a specified start vertex. It is a greedy method: at each step it uses the nearest vertex not yet visited, rather than comparing complete future tours.

Start at the stated vertex. Move to the nearest unvisited vertex, record that edge and mark the new vertex visited. Repeat until every vertex has been visited exactly once, then include the closing edge back to the start. Add every selected edge, including the closing edge, to obtain an upper bound.

If two nearest unvisited vertices tie, branch at the tie and complete each possible route; the branches can produce different tour lengths. Apply the same tie rule again if another tie occurs. For one start vertex, retain the shortest valid tour generated by its branches.

In a complete graph let $AB=2$, $AC=5$, $AD=6$, $BC=4$, $BD=3$ and $CD=1$. Starting at $A$, choose $B$ (2), then $D$ (3), then $C$ (1), and finally return to $A$ (5). The nearest-neighbour tour is $A-B-D-C-A$ with length 11.

Different starting vertices can give different tours. If several starts are requested, run the algorithm independently from each and take the smallest resulting tour length as the best nearest-neighbour upper bound. On a practical network, work from its complete shortest-distance table and then expand the selected edges into actual paths.