Un gráfico r -regular aleatorio es un gráfico seleccionado de, Que indica el espacio de probabilidad de todos los r gráficos -Regular en n vértices, donde 3 ≤ r < n y nr es par. [1] Por lo tanto, es un tipo particular de gráfico aleatorio , pero la restricción de regularidad altera significativamente las propiedades que se mantendrán, ya que la mayoría de los gráficos no son regulares.
Propiedades de gráficos regulares aleatorios
Al igual que con los gráficos aleatorios más generales , es posible probar que ciertas propiedades de los gráficos r -regulares aleatorios se mantienen asintóticamente casi con seguridad . En particular, para, un gráfico r -regular aleatorio de gran tamaño está asintóticamente casi con seguridad r -conectado . [2] En otras palabras, aunque r gráficos -Regular con conectividad menos de r existir, la probabilidad de seleccionar un gráfico tal tiende a 0 como n aumenta.
Si > 0 es una constante positiva y d es el menor número entero que satisface
entonces, asintóticamente casi con seguridad, un gráfico r -regular aleatorio tiene un diámetro como máximo d . También hay un límite inferior (más complejo) en el diámetro de los gráficos r -regulares, de modo que casi todos los gráficos r -regulares (del mismo tamaño) tienen casi el mismo diámetro. [3]
También se conoce la distribución del número de ciclos cortos: para m fijo ≥ 3, sea Y 3 , Y 4 ,…, Y m el número de ciclos de longitudes hasta m . Entonces las Y i son variables aleatorias de Poisson asintóticamente independientes con medias [4]
Algoritmos para gráficos regulares aleatorios
No es trivial implementar la selección aleatoria de gráficos r -regulares de manera eficiente y sin sesgos, ya que la mayoría de los gráficos no son regulares. El modelo de emparejamiento (también modelo de configuración ) es un método que toma nr puntos y los divide en n cubos con r puntos en cada uno de ellos. Tomando una coincidencia aleatoria de los nr puntos, y luego contrayendo los r puntos en cada cubo en un solo vértice, se obtiene un gráfico r regular o multigrafico . Si este objeto no tiene múltiples aristas o bucles (es decir, es un gráfico), entonces es el resultado requerido. Si no es así, es necesario reiniciar. [5]
Brendan McKay y Nicholas Wormald desarrollaron un refinamiento de este método . [6]
Referencias
- ^ Béla Bollobás , Random Graphs , 2nd edition, Cambridge University Press (2001), sección 2.4: Random Regular Graphs
- ^ Bollobás, sección 7.6: Gráficos regulares aleatorios
- ^ Bollobás, sección 10.3: El diámetro de los gráficos regulares aleatorios
- ^ Bollobás, sección 2.4: Gráficos regulares aleatorios (Corolario 2.19)
- ^ N. Wormald, "Modelos de gráficos regulares aleatorios", en Encuestas en combinatoria , Cambridge University Press (1999), págs. 239-298
- ^ B. McKay y N. Wormald, "Generación uniforme de gráficos regulares aleatorios de grado moderado", Journal of Algorithms , vol. 11 (1990), págs. 52-67: [1]