Valor esperado del número de aristas de un gráfico conectado

Question

Hay n vértices. 2 vértices se eligen de modo que no hay ningún borde entre ellos y añadir un borde entre ellos. Elegimos cada par con igual probabilidad. Una vez que tenemos una completamente conectado gráfico podemos dejar de añadir bordes. Sea X el número de aristas antes de obtener un grafo conexo. ¿Cuál es el valor esperado de X?

Por ejemplo, cuando el número de vértices son 4

caso 1:> 3 aristas forman un triángulo, y necesitamos un 4 de borde para hacer un gráfico completamente conectado.

caso 2:> todos los 4 nodos están conectados por 3 bordes.

La probabilidad de que el caso 1 es 4/20 (número de triple a de los bordes que hacer un triángulo dividido por el número de maneras en que podemos elegir 3 diferentes aristas), y la probabilidad de que el caso 2 es 16/20. Por lo que el valor esperado 4/20*4 + 16/20*3 = 3.2

Miré a través de http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model para obtener la respuesta. Sin embargo, no tuve la menor idea.

También me miró a través de http://www.cs.berkeley.edu/~jfc/cs174/lecs/lec9/lec9.pdf no se ha demostrado que el valor esperado es (n-1)*((n-1)st número Armónico). El uso que para n=4 obtenemos 3 * 1.83 = 5.5 Pero, la respuesta que estoy buscando es de 3.2.

Ahora, ¿hay una fórmula matemática para obtener la respuesta directamente? Por favor, muéstrame el camino. Soy un noob en matemáticas.

Edit1: El número de aristas que debemos considerar es (n-1) (n-1)(n-2)/2. El mínimo número de aristas de un grafo conexo es (n-1). El máximo para esta pregunta es (n-1)(n-2)/2 + 1. Esto es debido a que (n-1) aristas pueden ser conectados por máxima (n-1)(n-2)/2 aristas, y 1 edge para conectarse a la solitaria vértice.

Answer 1

Sea$P$ el conjunto de$n(n-1)/2$ de bordes potenciales (pares no ordenados en${1,\ldots,n}$). Para cada$S \subseteq P$ let$A(S)$ es el número esperado de bordes a añadir, comenzando con el gráfico con el conjunto de aristas$S$, hasta que obtenga un gráfico conectado. Así,$A(S) = 0$ iff el gráfico con aristas$S$ está conectado, y de lo contrario$$A(S) = 1 + \sum_{e \notin S} A(S \cup \{e\})/(n(n-1)/2 - |S|)$ $ La respuesta que desea es$A(\emptyset)$. Por supuesto esto no va a ser práctico para calcular si$n$ es grande.

Answer 2

La probabilidad de que un gráfico aleatorio de Bernoulli (ver página 4) con$pn^2/2$ de bordes esté conectado es aproximadamente$1-n(1-p)^n$. Así que si$p$ es un múltiplo enorme de$(\log n)/n$, entonces la probabilidad es muy cercana a 1. Para mí esto sugiere que el número esperado de bordes necesarios para hacer que el gráfico conectado realmente tiene orden de magnitud% Unesdoc.unesco.org unesdoc.unesco.org Pero esto no es, por supuesto, una fórmula exacta.