En matemáticas, se puede formar un árbol de expansión mínimo aleatorio asignando pesos aleatorios independientes de alguna distribución a los bordes de un gráfico no dirigido y luego construyendo el árbol de expansión mínimo del gráfico.
Cuando el gráfico dado es un gráfico completo en n vértices, y los pesos de los bordes 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ínimos aleatorios está limitado 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 al 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 borde que están distribuidos uniformemente en el intervalo unitario , la derivada es D = 1 y el límite es solo ζ (3) . [1] Para otros gráficos, el peso esperado del árbol de expansión mínimo aleatorio se puede calcular como una integral que involucra el polinomio de Tutte del gráfico. [2]
A diferencia de los árboles de expansión uniformemente aleatorios de gráficos completos, para los cuales el 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 gráficos completos tienen un diámetro típico proporcional a la raíz cúbica. [3] [4]
Se pueden utilizar árboles de expansión mínima aleatoria de gráficos de cuadrícula 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]
Referencias
- ^ Frieze, AM (1985), "Sobre el valor de un problema de árbol de expansión mínimo aleatorio", Matemáticas aplicadas discretas , 10 (1): 47–56, doi : 10.1016/0166-218X(85)90058-7 , SEÑOR 0770868
- ^ Steele, J. Michael (2002), "Árboles de expansión mínima para gráficos con longitudes de borde aleatorias", en Chauvin, Brigitte; Flajolet, Philippe; Gardy, Danièle; Mokkadem, Abdelkader (eds.), Matemáticas e informática II: algoritmos, árboles, combinatoria y probabilidades, Actas del segundo coloquio, Versalles-San Quintín, Francia, 16 al 19 de septiembre de 2002 , Tendencias en matemáticas, Basilea: Birkhäuser, págs. 223–245, doi :10.1007/978-3-0348-8211-8_14
- ^ Goldschmidt, Christina , Árboles de expansión mínima aleatoria, Instituto de Matemáticas, Universidad de Oxford , consultado el 13 de septiembre de 2019
- ^ Addario-Berry, Louigi; Broutin, Nicolás; Goldschmidt, Cristina; Miermont, Grégory (2017), "El límite de escala del árbol de expansión mínimo del gráfico completo", Annals of Probability , 45 (5): 3075–3144, arXiv : 1301.1664 , doi : 10.1214/16-AOP1132
- ^ Duxbury, primer ministro; Dobrin, R.; McGarrity, E.; Meinke, JH; Donev, A.; Musolff, C.; Holm, EA (2004), "Algoritmos de red y variedades críticas en sistemas desordenados", Estudios de simulación por computadora en física de materia condensada XVI: Actas del decimoquinto taller, Atenas, GA, EE. UU., 24 al 28 de febrero de 2003 , Actas de Springer en Física, vol. 95, Springer-Verlag, págs. 181-194, doi :10.1007/978-3-642-59293-5_25.
- ^ Foltin, Martin (2011), Generación automatizada de laberintos e interacción humana (PDF) , Tesis de diploma, Brno: Universidad de Masaryk, Facultad de Informática.
