Proof in Minimum Spanning Trees(More of a mathematical problem)

Question

As we know minimum spanning tree tries to achieve the "minimum" sum of weights of the tree.

Now my questions. Using prim and kruskal algorithms,

1) If we change what we are trying to minimize, "minimum" sum of weights of the tree to the W(T)= max eET{w(e)} where w(e) is the weight of an edge of the tree? i.e the maximum weight of the tree is minimum of all the other maximum edges of MSTs? Prove that prim and kruskal would work in this situation.

2) Now as metric we a want the "minimum" multiplication of weights of the edges of the tree. w(T) = ΠeΕT w(e). i.e the weight of this MST is the "minimum" multiplication of weights of the edges of the tree of all the other MSTs. Does the same apply here?

I know in 1) prim and kruskal will always work and achieve what we want and in 2) they will work but only under some conditions.

Could you give me an example in 2) where kruskal and prim would not work? Also for 1) how could i start in order to proof that prim and kruskal would always work, also same for 2)?

Thank you very much.

Answer 1

If all the edge weights are positive, then an MST as found by Prim's or Kruskal's will have the minimum sum(w(e)), and also the minimum sum(log(w(e))), and the minimum sum(log(w(e))) necessarily corresponds to the minimum product(w(e)). We can, in fact, replace the log with any monotonically increasing function.

If some of the weights are negative, however, then log(w(e)) is not always defined and this doesn't work, and an MST will not necessarily have the minimum product. An odd number of negative weights in the tree, for example, will always be better than an even number of negative weights, because it produces a negative product. The MST, however, will have the maximum number of negative weights, even if that maximum number is even.