写在前面

图论作业, 这次的作业相当于直接套公式了, 我就直接mathematica一套带走了.

问题

以Erodös and Rényi随机图为例,验证上述结论.

已知度分布:

\[p_k=\binom Nk p^k(1-p)^{N-k},\]

其中$N$为充分大的常数, $p$为参数(随机连边的概率), 求$G_0(x),G_1(x)$的表达式, 第一、二、三层邻居的期望$\langle k\rangle,\langle k_2\rangle,\langle k_3\rangle$, 并求参数$p$为何值时出现巨大连通分支?

解答

直接代入公式进行计算可以得到:

\[G_0(x)=\sum_{k=0}^\infty \binom Nk p^k(1-p)^{N-k}x^k=(1-p)^N \left(1-\frac{p x}{p-1}\right)^N=[p(x-1)+1]^N\] \[\begin{aligned} G_1(x) &=\frac{G_0'(x)}{G_0'(1)}=\frac{N p (1-p)^N \left(\frac{p (-x)+p-1}{p-1}\right)^N}{p (x-1)+1}\cdot \frac1{N p}\\ &=\frac{\left({1-p}\right)^{N} \left(\frac{p x+1-p}{1-p}\right)^N}{p (x-1)+1}=[p(x-1)+1]^{N-1} \end{aligned}\]

并且:

\[\begin{aligned} \langle k\rangle&=G_0'(1)=Np\\ \langle k_2\rangle&=G_0''(1)=(N-1) N p^2\\ \langle k_3\rangle&=G_0'''(1)=(N-2) (N-1) N p^3\\ \end{aligned}\]

当$\langle k\rangle-\langle k_2\rangle=0$, 即

\[\langle k\rangle-\langle k_2\rangle=Np-(N-1)Np^2=N p [1 - p(N - 1)]=0\]

时, 出现最大连通分支, 此时

\[p=0或\frac1{N-1}.\]

但$p=0$时不会连边, 所以$p=\dfrac1{N-1}$.