1
$\begingroup$

So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is at maximum instead of minimum.

In addition, let's say I want to find a spanning tree with the maximum product-sum weight (the product of the edges of the spanning tree is at its maximum).

Assuming edge-weights must be greater than 0, would their spanning trees contain the same edges? I'm pretty sure that their spanning trees are equal.

Plus, I also believe that a modified Kruskal's algorithm searching for maximum weighted edges would create these spanning trees since you'd want the largest weights for both types of maximum trees.

Is my thinking correct?

$\endgroup$
  • 2
    $\begingroup$ I doubt they'll always contain the same edges. Try some examples! Work systematically through a set of examples of small graphs, and see if you find a counterexample. I bet this will give you a lot of insight into your question. $\endgroup$ – D.W. Nov 6 '15 at 7:02
  • $\begingroup$ That's the thing, I tried various small graphs along with my TA and we couldn't differentiate the two. Since multiplication and addition are generally "put these two large things together to get something even bigger", and since all edge weights are greater than 0, the spanning trees always end up the same. $\endgroup$ – NotAStudentForReal Nov 6 '15 at 7:26
  • $\begingroup$ Try weights in $(0,1)$. $\endgroup$ – Raphael Nov 6 '15 at 8:42
  • $\begingroup$ "Assuming edge-weights must be greater than 0, would their spanning trees contain the same edges? I'm pretty sure that their spanning trees are equal." I don't understand what you mean. What does "they" refer to? $\endgroup$ – David Richerby Nov 6 '15 at 9:36
  • $\begingroup$ I was referring to the spanning trees of some graph given that I'm looking for a maximum spanning tree of that graph such that the total weight of the edges gives me the greatest sum and the greatest product-sum. $\endgroup$ – NotAStudentForReal Nov 7 '15 at 5:21
3
$\begingroup$

You state several beliefs but no reasoning. In math, if things are true then usually there is a good reason, namely a proof that the thing is true. Don't just make guesses, try to prove that your claims hold.

Regarding your conjecture, consider Kruskal's algorithm, modified so that it arranges the weights in decreasing rather than increasing order. If we apply any monotone increasing function on the weights, the algorithm would make exactly the same choices. Consider what happens when you replace each weight $w$ by its logarithm $\log w$. The weight of a spanning tree containing the edges $e_1,\ldots,e_{n-1}$ is then $$ \log w(e_1) + \cdots + \log w(e_{n-1}) = \log [w(e_1) \times \cdots \times w(e_{n-1})]. $$ In other words, after replacing all weights with their logarithms, you are actually computing the maximum spanning tree with respect to product. Since both algorithms compute the same spanning tree, your conjecture is correct.

$\endgroup$

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.