CUBE VERSUS TORUS MODELS AND THE EUCLIDEAN MINIMUM SPANNING TREE CONSTANT

We show that the length of the minimum spanning tree through points drawn uniformly from the d-dimensional torus is almost surely asymptotically equivalent to the length of the minimum spanning tree through points drawn uniformly from the d-cube. This result implies that the analytical expression recently obtained by Avram and Bertsimas for the minimum spanning tree (MST) constant in the d-torus model is in fact valid for the traditional d-cube model. We also show that the number of vertices of degree k for the MST in both models is asymptotically equivalent with probability 1. Finally we show how our results can be extended to other combinatorial problems such as the traveling salesman problem.

我们表明，从\(d\)维环面均匀抽取的点所构成的最小生成树的长度几乎必然渐近等价于从\(d\)维立方体均匀抽取的点所构成的最小生成树的长度。这一结果意味着，阿夫拉姆（Avram）和贝尔茨马斯（Bertsimas）最近针对\(d\)维环面模型中的最小生成树（MST）常数所获得的解析表达式实际上对传统的\(d\)维立方体模型也是有效的。我们还表明，在这两个模型中，最小生成树的度为\(k\)的顶点数量以概率\(1\)渐近等价。最后，我们展示了我们的结果如何能够扩展到其他组合问题，比如旅行商问题。