Christofides' Traveling Salesman Heuristic) Consider a symmetric traveling salesman problem where the arc costs are nonnegative and satisfy the triangle inequality (cf. the preceding exercise). Let R be a minimum cost spanning tree of the graph and let S be the subset of the nodes that has an odd number of incident arcs in R. A perfect matching of the nodes of S is a subset of arcs such that every node of S is an end node of exactly one arc of the subset and each arc of the subset has end nodes in S. Suppose that M is a perfect matching of the nodes of S that has minimum sum of arc costs. Construct a tour that consists of the arcs of M and some of the arcs of R, and show that its weight is no more than 3/2 times the optimal tour cost. Solve the problem of Fig. 10.18 using this heuristic, and find the ratio of the solution cost to the optimal tour cost.