New answers tagged minimum-spanning-tree
0
The important part is that you start with an MST for the original graph. With this extra piece of information, you can build a proof by contradiction, as follows:
Construct the new tree as described (add the edge, check the cycle, remove the edge with the largest weight), now assume for contradiction that this tree is not an MST. This may be for several ...
1
We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy.
To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected ...
Top 50 recent answers are included
