árbol de expansión mínima aleatorio

En matemáticas, se puede formar un árbol de expansión mínima aleatorio asignando pesos aleatorios independientes de alguna distribución a las aristas de un grafo no dirigido y, a continuación, construyendo el árbol de expansión mínima de dicho grafo.

Cuando el grafo dado es un grafo completo con n vértices y los pesos de las aristas tienen una función de distribución continua cuya derivada en cero es D > 0 , entonces el peso esperado de sus árboles de expansión mínima aleatorios está acotado por una constante, en lugar de crecer como una función de n . Más precisamente, esta constante tiende en el límite (cuando n tiende a infinito) a ζ (3)/ D , donde ζ es la función zeta de Riemann y ζ (3) ≈ 1,202 es la constante de Apéry . Por ejemplo, para pesos de aristas que se distribuyen uniformemente en el intervalo unitario , la derivada es D = 1 , y el límite es simplemente ζ (3) . ^{[ 1 ]} Para otros grafos, el peso esperado del árbol de expansión mínima aleatorio se puede calcular como una integral que involucra el polinomio de Tutte del grafo. ^{[ 2 ]}

A diferencia de los árboles de expansión aleatorios uniformes de grafos completos, cuyo diámetro típico es proporcional a la raíz cuadrada del número de vértices, los árboles de expansión mínimos aleatorios de grafos completos tienen un diámetro típico proporcional a la raíz cúbica. ^{[ 3 ] [ 4 ]}

Los árboles de expansión mínima aleatorios de grafos de cuadrícula pueden usarse para modelos de percolación de invasión de flujo de líquido a través de un medio poroso, ^{[ 5 ]} y para la generación de laberintos . ^{[ 6 ]}