Question 1: a) First, there is no loop and parallel edge needed to be removed in the initial graph. Choose any node as the root node, so let’s suppose that the root node is at S  v3 . Then, at each step, we check the outgoing edges and select the edge with less cost. Step 1: Step 2: Step 3: Step 4: Step 5: Step 6: Step 7: Step 8: Hence, a minimum spanning tree can be found using Prim’s Algorithm as follow: b) The cost of the minimum spanning tree using Prim’s Algorithm is calculated by 9  5  6  3  7 18  21  31  100 Question 2: a) First, we remove all loops and parallel edges. The graph remains unchanged. Next, we sort all edges in the increasing order of weight as follow v8  v9 : weight  3 v1  v 4 : weight  5 v 4  v8 : weight  6 v9  v10 : weight  7 v1  v3 : weight  9 v5  v9 : weight  12 v 4  v5 : weight  13 v6  v10 : weight  18 v3  v 4 : weight  19 v5  v6 : weight  21 v1  v 2 : weight  23 v 2  v5 : weight  31 v7  v8 : weight  57 Finally, we add the edges with smallest weight until all vertices shown Step 1: Step 2: Step 3: Step 4: Step 5: Step 6: Step 7: Step 8: Hence, the minimum spanning tree that can be found using Kruskal's Algorithm is shown below: b) The cost of the minimum spanning tree using Kruskal's Algorithm is calculated by 3  5  6  7  9 12 18  23  83 Question 3: A counter-example showing that the gr ...
Purchase document to see full attachment