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 grafo dado es un grafo completo en 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ínimos 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 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 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ínimo aleatorio se puede calcular como una integral que involucra el polinomio de Tutte del grafo. [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]
Los árboles de expansión mínimos aleatorios de gráficos de cuadrícula se pueden utilizar 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", Discrete Applied Mathematics , 10 (1): 47–56, doi : 10.1016/0166-218X(85)90058-7 , MR 0770868
- ^ Steele, J. Michael (2002), "Árboles de expansión mínima para gráficos con longitudes de aristas aleatorias", en Chauvin, Brigitte; Flajolet, Philippe; Gardy, Danièle; Mokkadem, Abdelkader (eds.), Matemáticas y Ciencias de la Computación II: Algoritmos, Árboles, Combinatoria y Probabilidades, Actas del 2º Coloquio, Versalles-St.-Quentin, Francia, 16-19 de septiembre de 2002 , Trends in Mathematics, Basilea: Birkhäuser, pp. 223-245, doi :10.1007/978-3-0348-8211-8_14
- ^ Goldschmidt, Christina , Árboles de expansión mínimos aleatorios, Instituto de Matemáticas, Universidad de Oxford , consultado el 13 de septiembre de 2019
- ^ Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; 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, PM; Dobrin, R.; McGarrity, E.; Meinke, JH; Donev, A.; Musolff, C.; Holm, EA (2004), "Algoritmos de redes y variedades críticas en sistemas desordenados", Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, EE. UU., 24-28 de febrero de 2003 , Springer Proceedings in Physics, 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 Masaryk, Facultad de Informática.
