Read N
Department of Physics, Yale University, P.O. Box 208120, New Haven, Connecticut 06520-8120, USA.
Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Sep;72(3 Pt 2):036114. doi: 10.1103/PhysRevE.72.036114. Epub 2005 Sep 14.
We consider minimum-cost spanning trees, both in lattice and Euclidean models, in d dimensions. For the cost of the optimum tree in a box of size L , we show that there is a correction of order L(theta) , where theta< or =0 is a universal d -dependent exponent. There is a similar form for the change in optimum cost under a change in boundary condition. At nonzero temperature T , there is a crossover length xi approximately T(-nu) , such that on length scales larger than xi, the behavior becomes that of uniform spanning trees. There is a scaling relation theta=-1/nu, and we provide several arguments that show that nu and -1/theta both equal nu(perc) , the correlation length exponent for ordinary percolation in the same dimension d , in all dimensions d> or =1 . The arguments all rely on the close relation of Kruskal's greedy algorithm for the minimum spanning tree, percolation, and (for some arguments) random resistor networks. The scaling of the entropy and free energy at small nonzero T , and hence of the number of near-optimal solutions, is also discussed. We suggest that the Steiner tree problem is in the same universality class as the minimum spanning tree in all dimensions, as is the traveling salesman problem in two dimensions. Hence all will have the same value of theta=-3/4 in two dimensions.
我们考虑d维晶格模型和欧几里得模型中的最小成本生成树。对于大小为L的盒子中最优树的成本，我们证明存在量级为L(θ)的修正，其中θ≤0是一个依赖于d的普适指数。在边界条件变化时，最优成本的变化也有类似形式。在非零温度T下，存在一个交叉长度ξ≈T(-ν)，使得在大于ξ的长度尺度上，行为变为均匀生成树的行为。存在一个标度关系θ = -1/ν，并且我们给出了几个论据表明在所有d≥1的维度中，ν和-1/θ都等于ν(perc)，即同一维度d中普通渗流的关联长度指数。所有论据都依赖于用于最小生成树的克鲁斯卡尔贪心算法、渗流以及（对于某些论据）随机电阻网络之间的紧密关系。还讨论了在非零小T时熵和自由能的标度，以及因此近最优解的数量的标度。我们认为在所有维度中，斯坦纳树问题与最小生成树属于同一普适类，二维中的旅行商问题也是如此。因此在二维中所有这些都将具有相同的θ = -3/4值。
