Minimal Spanning Trees for Graphs with Random Edge Lengths
Minimal Spanning Trees for Graphs with Random Edge Lengths
复制标题
具有随机边长的图的最小生成树
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
John M. Steele
中科院分区：
文献类型：
--
作者：
John M. Steele
从两个方向研究了边由独立同分布随机变量指定长度的连通图的最小生成树理论。首先，展示了在边长度均匀分布的模型下，如何利用连通图的Tutte多项式给出最小生成树长度的精确公式。其次，展示了局部弱收敛理论如何为MST长度和相关幂和的渐近理论提供了一个系统的方法。这些研究的结果包括：(1)精确合理地确定2≤n≤9的完整图Kn的MST的预期长度；(2)改进了Penrose（1998）关于d-cube的MST的结果，以及Beveridge， Frieze, and McDiarmid（1998）和Frieze， Ruzink6, and Thoma（2000）关于适度展开性质图的结果。在大多数情况下，这里审查的结果还没有达到最终形式，它们应该被视为正在进行的工作的一部分。
The theory of the minimal spanning tree (MST) of a connected graph whose edges are assigned lengths according to independent identically distributed random variables is developed from two directions. First, it is shown how the Tutte polynomial for a connected graph can be used to provide an exact formula for the length of the minimal spanning tree under the model of uniformly distributed edge lengths. Second, it is shown how the theory of local weak convergence provides a systematic approach to the asymptotic theory of the length of the MST and related power sums. Consequences of these investigations include (1) the exact rational determination of the expected length of the MST for the complete graph Kn for 2 ≤ n ≤ 9 and (2) refinements of the results of Penrose (1998) for the MST of the d-cube and results of Beveridge, Frieze, and McDiarmid (1998) and Frieze, Ruzink6, and Thoma (2000) for graphs with modest expansion properties. In most cases, the results reviewed here have not reached their final form, and they should be viewed as part of work-in-progress.