algorithm - Application of Prim's and Kruskal's other than finding MST

Question

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.

Answer 1

我猜作者的意思如下：

如果生成树上的最终分数是边权重在f(w1, w2, ... wn)哪里，那么权重应该是单调的。这意味着，如果你增加任何重量，要么总是增加（单调增加），要么总是减少（单调减少）。sum 和 product 都是单调递增的：wiff

f_sum (w1, w2, ... wn) = w1 + w2 + ... + wn
f_prod(w1, w2, ... wn) = w1 * w2 * ... * wn //non-negative-weights

对称是指顺序。f是对称的，如果你能确保f(..., wi, ..., wj, ...) = f(..., wj, ..., wi, ...)。应该清楚为什么需要这样做。任何 MST 算法都应该只关心要选择的边，而不是它们的顺序。sum 和 product 都是交换运算，因此是对称的。

之所以可行，是因为给定图的所有生成树都具有相同数量的边。如果你贪婪地取最大可用边（对于单调递增函数）或最小边（对于单调递减函数），你会自动最大化f.

我知道的大多数应用程序都是 MST 的应用程序（主要是为了逼近最佳解决方案）。就概率模型而言，最大乘积可以指最大化最终概率，其中边表示随后组合的单独事件的概率。我还没有偶然发现任何其他用于生成树构造的函数。