I saw a question in codechef where the objective is to select edges from a graph such that selected edges do not form a cycle and also product of weights of all the selected edges is maximum.In the editorial it is given that prim's and kruskal's algorithm works here.Infact it is given that it works for maximizing any symmetric monotonic function of edges. So what exactly is symmetric monotonic function and where else can we use this algorithms.
I guess what the authors mean is the following:
If your final score on the spanning tree is f(w1, w2, ... wn) where wi are the edge weights, then f should be monotonic in the weights. That means, if you increase any weight, f will either always increase (monotonically increasing) or always decrease (monotonically decreasing). Both the sum and product are monotonically increasing:
f_sum (w1, w2, ... wn) = w1 + w2 + ... + wn
f_prod(w1, w2, ... wn) = w1 * w2 * ... * wn //non-negative-weights
Symmetric refers to the order. f is symmetric if you can ensure that f(..., wi, ..., wj, ...) = f(..., wj, ..., wi, ...). It should be clear why this is needed. Any MST algorithm should only care about what edges to choose and not about their order. Both sum and product are commutative operations and therefore symmetric.
The reason why this works is because all spanning trees for a given graph have the same number of edges. If you greedily take the maximum available edge (for monotonically increasing functions) or the minimum edge (for monotonically decreasing functions), you will automatically maximize f.
Most applications I know of are applications of the MST (mostly to approximate an optimal solution). In terms of probabilistic models, the maximum product could refer to maximizing a final probability where the edges represent probabilities of separate events that are then combined. I haven't stumbled upon any other functions for spanning tree construction.