Gráfico regular aleatorio

Un gráfico aleatorio r -regular es un gráfico seleccionado de , que denota el espacio de probabilidad de todos los gráficos r -regulares en los vértices, donde y 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.${\displaystyle {\mathcal {G}}_{n,r}}$${\estilo de visualización n}$${\displaystyle 3\leq r<n}$${\estilo de visualización nr}$

Al igual que con los grafos aleatorios más generales , es posible demostrar que ciertas propiedades de los grafos aleatorios –regulares se cumplen asintóticamente casi con seguridad . En particular, para , un grafo aleatorio r -regular de gran tamaño está asintóticamente casi con seguridad r -conexo . ^[2] En otras palabras, aunque existen grafos –regulares con conectividad menor que , la probabilidad de seleccionar dicho grafo tiende a 0 a medida que aumenta. ${\estilo de visualización m}$${\displaystyle r\geq 3}$${\estilo de visualización r}$${\estilo de visualización r}$${\estilo de visualización n}$

Si es una constante positiva, y es el menor entero que satisface${\displaystyle \epsilon >0}$${\estilo de visualización d}$

${\displaystyle (r-1)^{d-1}\geq (2+\epsilon )rn\ln n}$

Entonces, de manera casi segura y asintótica, un grafo r -regular aleatorio tiene un diámetro como máximo de d . También existe un límite inferior (más complejo) para el diámetro de los grafos r -regulares, de modo que casi todos los grafos 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 , sea fijo el número de ciclos de longitudes hasta . Entonces son variables aleatorias de Poisson asintóticamente independientes con medias ^[4]${\displaystyle m\geq 3}$${\displaystyle Y_{3},Y_{4},...Y_{m}}$${\estilo de visualización m}$${\displaystyle Y_{i}}$

${\displaystyle \lambda _{i}={\frac {(r-1)^{i}}{2i}}}$

No es trivial implementar la selección aleatoria de grafos r -regulares de manera eficiente y sin sesgos, ya que la mayoría de los grafos 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 compartimentos con r puntos en cada uno de ellos. Al tomar una coincidencia aleatoria de los nr puntos y luego contraer los r puntos en cada compartimento en un solo vértice, se obtiene un grafo r -regular o multigrafo . Si este objeto no tiene múltiples aristas o bucles (es decir, es un grafo), entonces es el resultado requerido. Si no, se requiere un reinicio. ^[5]

Brendan McKay y Nicholas Wormald desarrollaron una versión más refinada de este método . ^[6]