随机最小生成树

在数学中，将一个无向图按照某种分布随机分配边权后可得一个新图，后者的最小生成树便称为随机最小生成树。

若给定的图是个顶点的完全图，且边权的分布函数处处连续并在原点处导数，则随机生成树的边权总和有上界，后者不随的增长而增长。更精确地讲，趋向于无穷大时，趋向于，其中为黎曼ζ函數，为阿培里常数。例如，若边权均匀分布于单位区间，则其导数为，趋向于无穷大时，恰趋向于。

的随机生成树在多孔介质中液态流体的模型以及算法中都有所应用。

参考资料

图论