隨機最小生成樹

在數學中，將一個無向圖按照某種分布隨機分配邊權後可得一個新圖，後者的最小生成樹便稱為隨機最小生成樹。

若給定的圖是 $n$ 個頂點的完全圖，且邊權的分布函數處處連續並在原點處導數 $D > 0$ ，則隨機生成樹的邊權總和有上界 $C$ ，後者不隨 $n$ 的增長而增長。更精確地講， $n$ 趨向於無窮大時， $C$ 趨向於 $ζ (3)/ D$ ，其中 $ζ$ 為黎曼ζ函數， $ζ (3)$ 為阿培里常數。例如，若邊權均勻分布於單位區間，則其導數為 $D = 1$ ， $n$ 趨向於無窮大時， $C$ 恰趨向於 $ζ (3)$ 。^[1]

網格圖（英語：grid graph）的隨機生成樹在多孔介質中液態流體的入侵滲透（英語：invasion percolation）模型^[2]以及迷宮生成（英語：maze generation）算法^[3]中都有所應用。

參考資料

^ 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 .
^ 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 .
^ Foltin, Martin, Automated Maze Generation and Human Interaction (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics, 2011 [2017-01-10], （原始內容 (PDF)存檔於2014-05-13） .

這是一篇關於數學的小作品。您可以透過編輯或修訂擴充其內容。

[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 [2017-01-10], （原始內容 (PDF)存檔於2014-05-13） .

[1]

[2]

[3]