Tenemos un país que contiene el $N$ ciudades con la carretera entre dos ciudades (lo que es un país pobre). Cada día podemos elegir dos ciudades que no hay ningún camino entre ellos y la construcción de un camino entre ellos. Elegimos cada par de no-conectados ciudades con igual probabilidad. Deje $X$ el número de días hasta la obtención de la conexión de un país. ¿Cuál es el valor esperado de $X$?
Un amigo me preguntó, yo no tengo ni idea todavía.
Esto es realmente un clásico resultado en la teoría de grafos aleatorios. El modelo que usted describe es conocido como el Erdos-Renyi azar gráfico de proceso $(G(n,M))_{M=0}^{n(n-1)/2}$: $G(n,0)$ es un vacío de la gráfica en la $n$ vértices; obtenemos $G(n,M+1)$ $G(n,M)$ mediante la inserción de un no-borde elegido uniformemente al azar.
En términos de distribución marginal, $G(n,M)$ es un gráfico en el conjunto de vértices $[n]$ $M$ bordes, elegido con igual probabilidad.
Esto se abordó en el papel que en realidad comenzó el estudio de los grafos aleatorios:
P. Erdos y A. Renyi. En Grafos Aleatorios I. Publicationes Mathematicae, 6:290-297, 1959.
El papel se puede ver en línea aquí.
El líder plazo en el número esperado de bordes para obtener conectividad es $\frac{1}{2}n\log n$. De hecho, si $$ M=\frac{n\log n+cn}{2}, $$ donde $c=c(n)\rightarrow\infty$ $n\rightarrow\infty$ (no importa cuán lentamente), entonces la probabilidad de que $G(n,M)$ está conectado tiende a 1 con $n$. Por otro lado, si $c=c(n)\rightarrow-\infty$$n\rightarrow\infty$, entonces la probabilidad de la conexión tiende a 0.
¿Por qué es $\frac{n\log n}{2}$ el umbral? Resulta que este es el umbral para la propiedad de tener grado mínimo de 1... y que es muy improbable que un gráfico de contar con un mínimo de grado 1 y no estar conectado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
