3
$\begingroup$

Assume we have non-distinct edge weights and multiple Minimum Spanning Trees may exist.

If we are given an edge, from A-B, how can we check (in linear time) if this edge is part of some MST?

Right now, I am considering a solution based on the cycle property. We look at all the edges with a weight less than our edge under consideration. If we can build a path utilizing the smaller edges via Depth First Search, we can say that our edge is not part of any MST.

Is my method correct?

If not, should I be looking at something else?

$\endgroup$
4
$\begingroup$

You need to take all the edges with strictly smaller weight, and then your method is correct. To prove it formally you need two things:

  • if the edge in question belongs to some cycle, then it would be skipped in any run of Kruskal's algorithm;
  • if it is not a part of some cycle, then it would not be skipped in some run of Kruskal's algorithm (in fact in any run that takes our edge as fast as it is possible).

First holds because any discarded edge must have been a part of some cycle, so there will be another cycle that would contain our edge. Second is true, because if we remove some edges, our edge still won't create a cycle.

Have fun ;-)

$\endgroup$
  • $\begingroup$ Thanks--2nd question of mine you've answered, you rock! This is in line with Prim's as well, correct? $\endgroup$ – quannabe Mar 1 '13 at 0:26
  • $\begingroup$ @quannabe I think so, but the proof probably is more tricky as you don't have that much control over the order of edges you consider. $\endgroup$ – dtldarek Mar 1 '13 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.