Probabilidad de que un grafo no dirigido tiene ciclos

Question

Si conocemos la probabilidad de $P$ que existe una arista entre dos vértices de un grafo no dirigido, vamos a decir $P= 1/v$ donde $v$ es el número de vértices en la gráfica, ¿cuál es la probabilidad de que el grafo tiene ciclos?

He torcido mi cerebro con este. Alguien puede ayudar?

Answer 1

Si una forma cerrada para esta probabilidad eran conocidos por el general $p$, se podría sustituir la $p=1/2$ a que para obtener la $2^{-v(v-1)/2}$ multiplicado por el número de los bosques en la $v$ etiquetado de los vértices. Este es OEIS secuencia A001858. La página da una exponencial de generación de función y una relación de recurrencia para esta secuencia, pero no de la forma cerrada, por lo que, presumiblemente, no la forma cerrada es conocido. Parece poco probable que el caso especial $p=1/v$ es más fácil de resolver, así que yo esperaría que usted no encontrará una forma cerrada para esto.

El número de $T(v,k)$ de los bosques en la $v$ vértices etiquetados con $k$ bordes está dada por OEIS secuencia A138464. La página proporciona relaciones de recurrencia. Puede utilizar estos números para encontrar el deseado de probabilidad como

$$ \sum_{k=0}^{v-1}p^k(1-p)^{v(v-1)/2-k}T(v,k)\;. $$

Answer 2

Si el gráfico es conocido por ser conectados: El grafo no tiene ciclos iff es un árbol.

Por Cayley de la fórmula, el número de árboles que se pueden formar con $v$ vértices es $v^{v-2}$

Un árbol con $v$ vértices ha $v-1$ bordes. La probabilidad de que un árbol puede estar formado es

$P^{v-1}\cdot(1-P)^{k-v+1}$

donde

$k=v\cdot(v-1)/2$,

la adición de hasta

$v^{v-2}\cdot P^{v-1}\cdot(1-P)^{k-v+1}$.

En el caso de que el gráfico se puede desconectar es complicado. Toma las distintas combinaciones de desconectado gráficos. Yo aun no visto un estudio sobre esto y que no tienen una mina de aquí.

EDIT: joriki la solución parece ser que la cubrían para el caso general.