Part B: (4.5 points) 3. A truck stationed at the depot (location 0) is to serve the demand of sales points 1 through 7, depicted in Figure 1, using a single tour. The distances between the depot and the sales points are given in Table 1. The network is symmetric. (3 points) 0 1 2 0 27.9 1 2 3 4 5 6 7 54.6 42.0 56.5 37.0 30.9 34.1 67.2 25.6 28.8 48.4 57.4 21.6 60.5 95.8 18.8 60.4 52.1 39.4 43.1 70.2 12.2 77.2 84.5 44.4 567 51.6 34.0 59.3 Table 1: Distances between depot and sales points 1 Figure 1: Geographic Locations of Depot and Sales Points 3a) The first step of Christofides heuristic is to find the minimum spanning tree on the network. Use Kruskal's algorithm to identify the MST on the network, and draw your solution on the copy of the network provided. Also, provide a list of the edges that you added to the MST, in the order that you added them. 7 0 List of edges added: Figure 2: Minimum spanning tree 3b) The second step of Christofides heuristic is to identify the set of nodes S with odd degree with respect to the minimum spanning tree, and then find the minimum cost perfect node matching, W, of the nodes in S. In the minimum spanning tree you identified in (a), there should be 6 nodes with odd degree with respect to the minimum spanning tree: S {1, 2, 3, 4, 6, 7). If this is not the case, go back and rework your solution before proceeding. One of the pairs in the minimum cost perfect matching W* is (1,4). Determine the two additional pairs included in W*, and show your work.