Problem
Let G = (V,E) be the graph with V = {a,b,c,d,e} and edges with weights p(ab) = p(cd) = p(de) = 10; p(ac)=p(ad)=p(bd)=p(be)=9; p(bc)=p(ae)=19 and p(ce)=20.
1) Determine the optimum solution for the Travel Salesman Problem and the solution obtained through Christofides Algorithm.
2) Detail each step of the solution with the intermediate algorithms, trees and graphs.