En un gráfico al azar de $n$ vértices, ¿cuál es el valor esperado del número de trazados simples?

Question

Soy muy nuevo en efectos discretos y fue esta pregunta:

En un gráfico al azar $G$ en $n$ vértices (cualquier borde puede ser en el gráfico con efectos de $\frac{1}{2}$,) ¿Cuál es el valor esperado del número de caminos entre un vértice $v$y un vértice $u$? (La respuesta puede ser una suma).

¿¿Exactamente comenzamos esto? Sé que tenemos que definir $f(u,v) = \text{number of simple paths between v and u}$, y necesitamos calcular el $E[f(u,v)] = \sum_{u,v \in \omega} {f(u,v) \cdot Pr(u,v)}$. Pero ¿qué es $f(u,v)$ aquí y cuál es nuestro $\omega$?

Answer 1

Aquí es donde usted debe utilizar la linealidad de las expectativas. En lugar de tratar de contar el número de simples trazos en una configuración determinada, contar el número de veces que un camino está en una configuración.

Dado cualquier camino simple entre el $u,v$ de la longitud de la $l$, el número esperado de veces que va a ser una ruta de acceso es $\left(\frac{1}{2}\right)^l$. Por lo tanto tenemos que la suma sobre todas las rutas de acceso entre el $2$ vértices $uv$.

Fix $k$. Cuántos simples caminos de longitud $k+1$ desde $u$$v$? No debe ser $k+2$ vértices involucrados, de los cuales el inicial y final de los vértices se $u$$v$. A continuación, tenemos que escoger el $k$ restante de los $n-2$ vértices. El orden en el que los vértices son recogidos de la materia, por lo tanto, hay $(n-2)^{\underline k} = k!{n-2\choose k}$ simple caminos de longitud $k+1$ entre los vértices $u, v$.

$$E[X] = {n \choose 2} \left[ \sum_{k=0}^{n-2} k!{n-2\choose k} \times \frac{1}{2^{k+1}}\right]$$