Question
Please help with exercise 12.3
Exercise 12.3. We are given a connected undirected graph G = (VE) with positive edge weights. Assume that all the edge weights are distinct The operation of contracting an edge e - (u, v) in G involves the following operations: (1) remove the vertices u andv and introduce a new vertexx; (2) for each edgee' having an endpoint in either u orv do: replace the endpoint u or u by x, i.e., ife' : (u,u) (ore'-(mu)) ?t is replaced by the edge e(,). (For this problem, we can assume that each edge comes with a distinct label. When we contract edges, we use the same labels on the edges, as they were before contraction, for easy identification. For example, in the above example, the edge label for e' remains the same after contraction as well, despite the endpoints changing.) Consider the following algorithm for finding a minimum spanning tree: 1. repeat until G ha 2. 3. 4 5. 6. s one vertex for each vertexv E G do Select the minimum-weight edge incident on v Contract all the selected edges chosen in Step 3. Eliminate self-loops. Eliminate all but the lowest-weight edge among each set of multiple edges (i.e., edges that go across the same pair of vertices) 7 endrepeat 8. Output all the edges selected in Step 3 as the MST edges. a) Show that the minimum spanning tree of G is unique if all the edge weights are distinct. (Hint: One way to show this is proof by con tradiction: assume two distinct minimum spanning trees and get a contradiction.) b) Argue that the above algorithm correctly outputs the edges of the min- imum spanning tree. (Hint: Use the cut property of Exercise 12.2.) c) Give a tight (up to a constant factor) upper bound on the number of iterations (one iteration is execution of Steps 2-6) of the algorithm. d) Show how to implement one iteration of the algorithm in O(V+EI) time. (Hint: Use depth-first search.) Using your answer to part (d), what is the (overall) running time of the algorithmi? e) Suppose the edge weights are not distinct. Will the algorithm still work? Ifyour answer is "no'", then show how to fix it
Explanation / Answer
Solution:
a)
Suppose there are two spanning trees in of the graph,
so now this means that both the spanning trees will have the same cost,
This means that they both will have n-1 edges, but since all the edges have distinct edge weights then this is a contradiction that the edges are not same.
This proves that there will be a unique minimum spanning tree.
b)
The above algorithm outputs correct minimum spanning tree because of the below reasons:
c)
The operation is being done at every vertex and the edges connected to it
so the tightest bound will be
o(||E|* |E|)
d)
add one line to choose from the vertex point of view
apply DFS to check if the vertex is already visited.
e)
No,
If there is a cycle of length 3 or more then this algorithm will fail, to fix this add one more line before step 6 to remove the highest edge weight of the from cycle of length or more.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)