Let G(V, E) be an undirected graph with positive weights on its edges. Assume th
ID: 3593686 • Letter: L
Question
Let G(V, E) be an undirected graph with positive weights on its edges. Assume that edges are given in an increasing order of weights. So E- [e1... em^ where Given a real value r, let Gr denote the graph obtained from G(V, E) be removing from E every edge whose weight is strictly larger than r. That is, Gr contains only the edges whose weight is r or smaller than r. For example, Gw(ei)-0.000001 contains no edges, Gu(es) contains 5 edges, and Gw(em) con- tains all the edges of E. We say that is the critical value of G(V. E) if connected. is connected, by -0.00001 is not Suggest an 0(m log m) time algorithm for finding .Explanation / Answer
ANSWER:
basically, here we need to find a Minimum Cost Spanning Tree (MST) of the given graph.
The Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees.
One of the famous algorithms for finding MST is Kruskal's algorithm.
Steps followed in Kruskal's algorithm are:
1. Sort all edges of graph in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree; where V is the number of edges.
So, using these steps we can find the subgraph Geta. Step 1 is already done for us. Questions says that edges are already given in sorted order.
Now, let's analyze the time complexity of this algorithm.
Let E be the number of edges and V be the number of vertices in the original graph.
Sorting of edges takes O(ELogE) time. This step is already done for us though. After sorting, we iterate through all edges and apply find-union algorithm to check whether the edge is forming a cycle or not. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be at most O(V^2), so O(LogV) and O(LogE) are same. Therefore, the overall time complexity is O(ElogE) or O(ElogV).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.