¿Cuál es la probabilidad de que un grafo que contiene n nodos con k aristas aleatorias cada uno esté fuertemente conectado?

Question

Considere un grafo no dirigido "aleatorio", con n nodos y (por término medio) k aristas asignadas a cada nodo, de forma que la arista conecte el nodo con un nodo elegido al azar en el grafo. ¿Cuál es la probabilidad de que este grafo esté conectado, es decir, que contenga un camino desde cada nodo a cualquier otro nodo?

Answer 1

Permítanme primero introducir algo de terminología: $G(n,p)$ es un grafo aleatorio en $n$ vértices en los que cada arista se pone con probabilidad $p$ .

Un resultado clásico en la teoría de grafos aleatorios establece que si $p = \frac{\log n + c}{n}$ (donde $c$ es constante) entonces la probabilidad de que un gráfico dibujado según $G(n,p)$ está conectado tiende a $e^{-e^{-c}}$ como $n \to \infty$ .

Utilizando esto, se puede demostrar que si $c(n) \to -\infty$ y $p = \frac{\log n + c(n)}{n}$ entonces la probabilidad de que un gráfico dibujado según $G(n,p)$ está conectado tiende a $0$ y si $c(n) \to \infty$ la probabilidad tiende a $1$ .

Puede obtener resultados similares en el $G(n,m)$ en el que se pone $m$ bordes aleatorios. En este caso, en lugar de $p = \frac{\log n + c}{n}$ debe tener en cuenta $m = \frac{n}{2} (\log n + c)$ .

Por último, si sortea un $d$ -grafo regular en $n$ vértices para $d \geq 3$ entonces la probabilidad de que esté conectado tiende a $1$ como $n \to \infty$ . (Para $d = 2$ tiende a $0$ .)

Answer 2

Véase wikipedia sobre el modelo Erdos-Renyi. Dos propiedades clave son:

1. Si $pn<(1-\epsilon)\log n$ entonces es casi seguro que el gráfico está desconectado.

2. Si $pn>(1+\epsilon)\log n$ entonces es casi seguro que el grafo es conexo.