En matemáticas, se puede formar un árbol de expansión mínimo aleatorio asignando pesos aleatorios 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á 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 va al infinito) a ζ (3) / D , donde ζ es la función zeta de Riemann y ζ (3) es la constante de Apéry . Por ejemplo, para los pesos de los bordes que se distribuyen uniformemente en elintervalo unitario , la derivada es D = 1 y el límite es solo ζ (3) . [1]
En contraste con los árboles de expansión aleatorios uniformemente 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. [2]
Los árboles de expansión mínima aleatoria de los gráficos de cuadrícula se pueden utilizar para modelos de infiltración de invasión del flujo de líquido a través de un medio poroso, [3] y para la generación de laberintos . [4]
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 , MR 0770868.
- ^ Goldschmidt, Christina , árboles de expansión mínimos aleatorios , Instituto de Matemáticas, Universidad de Oxford , consultado el 13 de septiembre de 2019
- ^ Duxbury, PM; 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, 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.