Please show the steps you took to get the maximal independent set, mimimal vertex cover, maximal clique and minimum connected dominating set for Q1 and please show all work for question Q2. So I will know what to do for each problem.

21:25 pts) For the graph assigned to you, find the following using the approximation heuristics liscussed in class. (a-7) Maximal Independent Set (b-2) Minimal Vertex Cover (c-8) Maximal Clique (d-8) Minimum Connected Dominating Set Show all the work for each. 02: 20 pts) You are assigned the edge weight matrix for a complete graph. Determine an approximation to the minimum weight tour using the (i-8) Nearest neighbor heuristic (i-12) Twice around the tree heuristic. Also, show one attempt of reducing the tour weight using the 2-change heuristic for the with each of the two heuristics. i tour obtained Show all the work as well as clearly indicate the tour and its weight before and after the using the 2-change heuristic in each case. attempt of V 107 o12 3 5 V4 15 3 12 O 510 Vs 14 350 Vo lo 8 15 ioO