Problem Detail: 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?
Asked By : NotAStudentForReal
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49140
