NEED HELP WITH THESE PROBLEMS PLEASE.

Page of 8 ZOOM 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. 6 Figure 2: Minimum spanning tree List of edges added: 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. Page of 8 ZOOM 3c) Draw the minimum spanning tree again on the network below, but this time, also include the arcs in W. as dotted lines. Then, specify a tour of the nodes that uses each are in your diagram exactly once. Note that in order to use each arc exactly once, you will visit some nodes more than once in the tour T. Figure 3: Minimum spanning tree with perfect node matching Tour using each arc in this diagram: 3d) Complete Christofides heuristic by introducing shortcuts to avoid revisiting nodes in T', such that a feasible solution to this instance of TSP results. Draw your TSP tour on the diagram provided. Indicate the cost of the TSP tour. Figure 4: TSP tour Cost of TSP tour: Page of 8 ZOOM 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. 6 Figure 2: Minimum spanning tree List of edges added: 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. Page of 8 ZOOM 3c) Draw the minimum spanning tree again on the network below, but this time, also include the arcs in W. as dotted lines. Then, specify a tour of the nodes that uses each are in your diagram exactly once. Note that in order to use each arc exactly once, you will visit some nodes more than once in the tour T. Figure 3: Minimum spanning tree with perfect node matching Tour using each arc in this diagram: 3d) Complete Christofides heuristic by introducing shortcuts to avoid revisiting nodes in T', such that a feasible solution to this instance of TSP results. Draw your TSP tour on the diagram provided. Indicate the cost of the TSP tour. Figure 4: TSP tour Cost of TSP tour