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?
Respuesta
¿Demasiados anuncios?
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.
