1
$\begingroup$

Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it?

I can't seem to think of a way to make a distinction between the same weights, it feels unnatural.

$\endgroup$

1 Answer 1

3
$\begingroup$

Though the Borůvka's algorithm (wiki) for minimum spanning tree is (sometimes? often?) described for weighted graphs with distinct edge weights, this treatment is only for convenience.

If we have an algorithm that assumes the edge weights are unique, we can use it on graphs where multiple edges have the same weight, as long as we have some way of breaking the ties. For example, in graphs where edges have identical weights, edges with equal weights can be ordered based on the lexicographic order of their endpoints (suggested by the wiki article).

To apply the lexicographic order, assume two edges $(a,b)$ and $(c,d)$ have the same weight $w(a,b) = w(c,d)$, where $a,b,c,d$ are (not necessarily distinct) vertices. Then we can decide which of $w(a,b)$ and $w(c,d)$ have the "smaller" weight by comparing the pair $(a,b)$ and $(c,d)$ in their lexicographic order.

Therefore, you don't need to re-weight the equally-weighted edges. You only need to mark them distinct.

$\endgroup$
3
  • $\begingroup$ How would you implement the lexicographic order for a graph? $\endgroup$
    – Milan
    Jan 26, 2015 at 5:09
  • 1
    $\begingroup$ @Milan See my update. $\endgroup$
    – hengxin
    Jan 26, 2015 at 5:17
  • $\begingroup$ Thank you for this useful clarification! Somehow I was unable to see a similar explanation of the need of the "just tie breaking resolver" rather than true unique graph weights. $\endgroup$ Jun 4, 2018 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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