随机最小生成树

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

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

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

参考资料

Frieze, A. M., , Discrete Applied Mathematics, 1985, 10 (1): 47–56, MR 770868, doi:10.1016/0166-218X(85)90058-7.
Duxbury, P. M.; Dobrin, R.; McGarrity, E.; Meinke, J. H.; Donev, A.; Musolff, C.; Holm, E. A., , , Springer Proceedings in Physics 95, Springer-Verlag: 181–194, 2004, doi:10.1007/978-3-642-59293-5_25.
Foltin, Martin, (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics, 2011.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Frieze, A. M., , Discrete Applied Mathematics, 1985, 10 (1): 47–56, MR 770868, 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., , , Springer Proceedings in Physics 95, Springer-Verlag: 181–194, 2004, doi:10.1007/978-3-642-59293-5_25.

[3] Foltin, Martin, (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics, 2011.