¿Cuál es el peso promedio de un árbol de expansión mínima de $n$ al azar puntos seleccionan en el cubo de la unidad?

Question

Supongamos que elegimos $n$ puntos al azar en la unidad de cubo en $\mathbb{R}_3$, $p_1=\left(x_1,y_1,z_1\right),$ $p_2=\left(x_2,y_2,z_2\right),$ etc. (Lo, $x_i,y_i,z_i$ $3n$ uniformemente distribuidos al azar entre variables $0$$1$.) Deje $\Gamma$ ser un grafo completo en estos $n$ puntos, y el peso de cada arista $\{p_i,p_j\}$ $$w_{ij}=\sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2+\left(z_i-z_j\right)^2}.$$

Pregunta: ¿Cuál es el valor esperado del peso total de un mínimo árbol de expansión de $\Gamma$?

(Nota: Aquí el peso total significa la suma de todas las aristas en el mínimo árbol de expansión.)

Un periférico de solicitud: La respuesta es, probablemente, una función de $n$, pero no tengo el poder de cómputo o una buena implementación de Kruskall del algoritmo para sugerir lo que debería ser su aspecto. Si alguien pudiera ejecutar una simulación para generar este promedio a lo largo de muchos a $n$, podría contribuir a una solución para ver estos datos.

Answer 1

Según el artículo de Wikipedia sobre el Euclidiana mínimo árbol de expansión (o EMST), se espera que el peso total es asintótica $$ c(d)n^{\frac{d-1}{d}}\int_{\mathbb{R}^{d}}f(x)^{\frac{d-1}{d}}dx $$ como $n\rightarrow\infty$ donde $d$ es la dimensionalidad (aquí, $d=3$), $f(x)$ es la densidad de probabilidad de la selección del punto (aquí, $f(x)=1$ dentro del cubo), y $c(d)$ sólo depende de la dimensionalidad. Para el uniforme de la selección dentro de la unidad de cubo, se espera que el tamaño debe satisfacer $$ E(n) \sim c_{3}n^{2/3} $$ para algunas constantes $c_{3}$.

Experimentos numéricos (por modesto $n$, hasta alrededor de $8000$) sugieren que la $c_{3}=0.65 \pm 0.01$.

Answer 2

Si $n = 0$ $n = 1$ la respuesta obviamente es 0. Si $n = 2$ tenemos $$E\left((x_1 - x_2)^2\right) = E(x_1^2 - 2x_1x_2 + x_2^2) = E(x_1^2) - 2E(x_1)\cdot E(x_2) + E(x_2^2) \\= \frac13 - 2\frac12\cdot\frac12 + \frac13 = \frac16.$ $ $y$ - y $z$-coordenadas. Así $E(w_{12}) = \sqrt{\frac16 + \frac 16 + \frac16} = \frac1{\sqrt2}$ y árbol de expansión contiene el % de borde $\{\,1, 2\,\}$solamente.

Veo que es posible considerar varios casos $n = 3$, sin embargo arbitrario $n$ no espero obtener la forma estrecha de la respuesta.