Menu
I am working on an algorithm to check if a given edge is included in one of all possible mst's.
For this question, we are considering non-distinct values and our edge e connects vertices A & B.
So far, I have: If a path can be made from A to B consisting of edges with weights less than or equal to the weight of our edge e--we can say that edge e is not a part of any MST.
Am I missing anything here/ ideas on a better algorithm?
EDIT:
What are thoughts on a solution involving the cycle property-- So, we consider all edges with weight less than the edge we are considering. If we can make a path from A->B with those edges, we can say that it is not part of any MST?
809
Just take a graph with two edges e1 and e2 between A and B that have the same weight. You should also consider a graph A-B-C with an additional edge from A-C where all edges have weight one. No matter which edge you remove you can get a minimal spanning tree. Thus any edge can be part of a MST.
Another theorem on characterization of an all-MST edge: an edge e appears in all MSTs if and only if there is a cut (S, T) of the graph such that e is the unique lightest edge crossing that cut.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
You can prove whether it has a unique MST in O(E log(V)) . First find a minimum spanning tree with standard techniques. Go back to your original tree, and replace all weights with pairs of numbers, the original weight, and then 0 or 1 based on whether or not it is in the MST you found.
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 always not the maximum weight edge in all the cycles that it is a part of.
80
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
