随机最小生成树

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

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

网格图英语grid graph的随机生成树在多孔介质中液态流体的入侵渗透英语invasion percolation模型[2]以及迷宫生成英语maze generation算法[3]中都有所应用。

参考资料编辑

  1. ^ Frieze, A. M., On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, 1985, 10 (1): 47–56, MR 0770868, doi:10.1016/0166-218X(85)90058-7 .
  2. ^ Duxbury, P. M.; Dobrin, R.; McGarrity, E.; Meinke, J. H.; Donev, A.; Musolff, C.; Holm, E. A., Network algorithms and critical manifolds in disordered systems, Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, USA, February 24–28, 2003, Springer Proceedings in Physics 95, Springer-Verlag: 181–194, 2004, doi:10.1007/978-3-642-59293-5_25 .
  3. ^ Foltin, Martin, Automated Maze Generation and Human Interaction (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics, 2011 .