A Note on Random Minimum Length Spanning Trees
A Note on Random Minimum Length Spanning Trees
复制标题
关于随机最小长度生成树的注记
DOI：
10.37236/1519
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
L. Thoma
中科院分区：
文献类型：
--
作者：
A. Frieze;M. Ruszinkó;L. Thoma
考虑一个连接的$ r $ -N $ n $ vertex图$ g $，随机独立边缘长度，每个均匀分布在$ [0,1] $上。令$ mst（g）$为最小跨树的预期长度。我们在本文中表明，如果$ g $已足够高度连接，那么最小跨越树的预期长度为$ \ sim {n \ a} \ zeta（3）$。如果我们省略了边缘连接条件，则最多是$ \ sim {n \ vos r}（\ zeta（3）+1）$。
Consider a connected $r$-regular $n$-vertex graph $G$ with random independent edge lengths, each uniformly distributed on $[0,1]$. Let $mst(G)$ be the expected length of a minimum spanning tree. We show in this paper that if $G$ is sufficiently highly edge connected then the expected length of a minimum spanning tree is $\sim {n\over r}\zeta(3)$. If we omit the edge connectivity condition, then it is at most $\sim {n\over r}(\zeta(3)+1)$.