.png){kind=icon}
.png){kind=icon}
返回
Models of Random Spanning Trees
.png){kind=icon}
PRE
AI
DOI：10.1002/rsa.70063.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
现有多种随机算法可用于生成给定基准图中的生成树；其中一些算法旨在生成树上的均匀分布（UST），而实践中最快且最常用的算法则是为边随机分配权重，然后采用贪心算法选择最小权重生成树（MST）。尽管MST在应用中是基础工具，但随机MST的数学性质远未像UST那样得到深入探索。本文我们开发了用于定量研究随机MST的工具。我们考虑了权重独立同分布（i.i.d.）地来自实数上的单一分布的标准情形，以及进一步推广至乘积测量的情形，其中权重独立地来自任意分布。
Keyword:
intransitive dice
Kruskal's algorithm
minimum spanning tree
redistricting
查看更多机构