2 votos

Probabilidad de las aristas de un grafo aleatorio con una secuencia de grados prescrita

Sea G un grafo generado aleatoriamente a partir de la secuencia de grados D = (d1, d2, .., dn) y x, y son vértices de G. ¿Cómo calcular la probabilidad de que (x, y) sea una arista de G?

2voto

user8134 Puntos 1273

Quiero mostrar, que su problema puede ser resuelto por la solución de $O(n)$ problema más común:

Problema 2: ¿Cuál es el número de grafos con grados $(d_1,\dots,d_n)$ ?

Vamos a denotar este número por $f(d_1,\dots,d_n)$ . Su función generadora es igual a $$F=F(z_1,\dots,z_n)=\prod_{i< j}(1+z_iz_j)\tag{1}$$ (asumiendo que las aristas múltiples y las aristas cíclicas no están permitidas). Para simplificar, supondré que $x$ es un primer vértice (con grado $d_1$ ) y $y$ es el segundo y $d_1\leq d_2$ . La probabilidad, que le interesa, es igual a $$p=1-g(d_1,\dots,d_n)/f(d_1,\dots,d_n)\tag{2},$$ donde $g(d_1,\dots,d_n)$ es igual al número de gráficos con grados $(d_1,\dots,d_n)$ que no contiene el borde $\{1,2\}$ . Su función generadora es igual a $$G=G(z_1,\dots,z_n)=\prod_{i< j;\{i,j\}\neq\{1,2\}}(1+z_iz_j),\tag{3}$$ por lo que tenemos $$F=(1+z_1z_2)G.\tag{4}$$ Por lo tanto, $$f(d_1,d_2,d_3,\dots,d_n)=g(d_1,d_2,d_3,\dots,d_n)+g(d_1-1,d_2-1,d_3,\dots,d_n)\tag{5}$$ y $$g(d_1,\dots,d_n)=\sum_{k=0}^{d_1} (-1)^k f(d_1-k,d_2-k,d_3,\dots,d_n).\tag{6}$$ A partir de (2) y (6) vemos que la resolución del problema 2 ( $d_1+1$ veces) es suficiente para calcular la probabilidad deseada.

Por supuesto, el problema 2 puede resolverse a tiempo $c(n(n-1)/2)(d_1+1)(d_2+1)\dots (d_n+1)$ pero creo que puedes intentar encontrar una solución mejor. El problema 2 podría ser un problema conocido de enumeración de grafos. Probablemente ya conozcas este libro pero si no lo haces, echa un vistazo.

i-Ciencias.com

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.

Powered by:

X