As before, assume that the given undirected weighted graph G = (V,E) has edges o
ID: 3574662 • Letter: A
Question
As before, assume that the given undirected weighted graph G = (V,E) has edges of distinct weights. Thus, G must have a unique MST T> For any cycle C of graph G, show that the heaviest edge f on C does not appear in the MST t. You can use the fact that an edge e exist in E appears in T if and only if e is a lgith edge crossing a certain cut. Make your answer concise. Probably, a couple of sentences should be enough. (Hint: suppose that f appears in T and derive a contradiction).
2. (10 points) As before, assume that the given undirected weighted graph G3 (V, E) has edges of distinct weights. Thus, G must have a unique MST T. For any cycle C of graph G, show that the heaviest edge f on C does not appear in the MST T. You can use the fact that an edge e EE appears in T if and only if e is a light edge crossing a certain cut. Make your answer concise. Probably, a couple of sentences should be enough. (Hint: suppose that f appears in T and derive a contradiction.)Explanation / Answer
Solution :
Hii there check this here.
For every cut of G, the unique light edge crossing the cut must be part of every MST of G. Consider the set T of edges, containing the unique light edge crossing each cut C of G. By the previous part, we know that T is a subset of every MST. Now we can show that T must be equal to every MST. Because there is exactly one edge of T crossing every cut of G, the graph (V, T) must have exactly one connected component: if there were two unconnected components V1 and V V1, then the cut (V1, V V1) would not be crossed by any edge of T, which contradicts the definition of T. In addition, T cannot contain any cycles: the heaviest edge on a cycle in T cannot be the unique lightest edge in any cut. Then T itself must be a spanning tree of G. Because T is a subset of all minimum spanning trees of G, it must be the unique MST of G, as any additional edge added to T would form a cycle, making it no longer be a tree. In a graph with no duplicate edge weights, there cannot be any ties for the light edge crossing a cut. As a result, any graph with distinct edge weights will satisfy the requirements for the theorem i, and will therefore have exactly one minimum spanning tree.
Check this theorem for further clarity:
Pick any cycle C in the graph and let e be the heaviest edge in that cycle. Then there is a minimum spanning tree that does not contain e.
Proof: Suppose there is a minimum spanning tree which contains e. If we add one more edge to the spanning tree we will create a cycle. Suppose we add edge ˆe to the spanning tree which generated cycle C. We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal which implies that e must not be in minimum spanning tree and we get a contradiction (b)Correctness of the algorithm follows from the lemma. Since we are looking at all the edges in decreasing weight, we are choosing the heaviest edge first. That edge must not be in the MST if it is part of a cycle C. Presented algorithm checks for a cycle and remove the edge from the graph if it is part of a cycle. (c)Linear time algorithm to check whether there is a cycle containing a specific edge e: Let e = (u, v). Start a DFS from u and exclude edge e while considering outgoing edges from u. Check if e is a back-edge in resultant DFS tree (d)Complexity Analysis: Total number of edges in a MST is given by |V | 1. Therefore on the worst case the algorithm will remove E |V | + 1 edges from G to obtain the MST. At each iteration of the algorithm, cycle detection takes O(V + E). Therefore total running time is given by O((|E| |V | + 1) · (V + E)).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.