Menu
I have the following problem on my homework:
Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph
(We are allowed to get help from others on this assignment, so this isn't cheating.)
I think that I could do a BFS and find if this edge is a edge between two layers and if so whether this edge was the smallest across those layers. But what could I say when this edge is not a tree edge of the BFS tree?
878
Run DFS to check if v and w are connected in G'. If v and w are still connected, then edge e doesn't belong to any minimum spanning tree. If v and w are not connected, then edge e is in some minimum spanning tree.
Minimum spanning tree. An edge-weighted graph is a graph where we associate weights or costs with each edge. A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.
Find an MST T of G. If it does not contain e, then you are done. Otherwise, set wt(e)=∞ and find an MST T′ of G with this modification. If T′ contains e or wt(T′)>wt(T), then e necessarily appears in every MST of G.
Step 1: Sort all edges in increasing order of their edge weights. Step 2: Pick the smallest edge. Step 3: Check if the new edge creates a cycle or loop in a spanning tree. Step 4: If it doesn't form the cycle, then include that edge in MST.
As a hint, if an edge is not the heaviest edge in any cycle that contains it, there is some MST that contains that edge. To see this, consider any MST. If the MST already contains the edge, great! We're done. If not, then add the edge into the MST. This creates a cycle in the graph. Now, find the heaviest edge in that cycle and remove it from the graph. Everything is now still connected (because if two nodes used to be connected by a path that went across that edge, now they can be connected by just going around the cycle the other way). Moreover, since the cost of the edge was deleted wasn't any smaller than the cost of the edge in question (because the edge isn't the heaviest edge in the cycle), the cost of this tree can't be any greater than before. Since we started with an MST, we must therefore end with an MST.
Using this property, see if you can find whether the edge is the heaviest edge on any cycle in linear time.
56
We will solve this using MST cycle property, which says that, "For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of all other edges of C, then this edge cannot belong to an MST."
Now, run the following O(E+V) algorithm to test if the edge E connecting vertices u and v will be a part of some MST or not.
Step 1
Run dfs from one of the end-points(either u or v) of the edge E considering only those edges that have weight less than that of E.
Step 2
Case 1 If at the end of this dfs, the vertices u and v get connected, then edge E cannot be a part of some MST. This is because in this case there definitely exists a cycle in the graph with the edge E having the maximum weight and it cannot be a part of the MST(from the cycle property).
Case 2 But if at the end of the dfs u and v stay disconnected, then edge E must be the part of some MST as in this case E is never the maximum weight edge of the cycles that it is a part of.
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
