树的一种生长模式
我们按照如下方式随机地构造一个图$G$。一开始，图$G$有$2$个顶点（标号为$1$和$2$）和连接这$2$个顶点的$1$条边：
1——2
接下来按照如下的方式不断地在图$G$中增加$1$个顶点和$1$条边，直到图$G$的顶点数达到$N$为止：
————————————————————
增加顶点之前，设$k$为图$G$的顶点数，那么新增的顶点的标号是$(k+1)$。
增加边之前，我们先从顶点$1$到$k$这$k$个顶点中随机选$1$个顶点，
某个顶点被选中的概率与这个顶点的度数成正比，
也就是说，顶点$i$（$1\leq i\leq k$）被选中的概率是${d(i)}/{2(k-1)}$，
其中，$d(i)$表示顶点$i$的度数，$2(k-1)$是顶点$1$到$k$的度数之和。
记顶点$x$是被选中的顶点，那么新增的边连接顶点$x$和顶点$(k+1)$。
————————————————————
例如：当$N=3$时，构造出来的图$G$有$2$种可能：
1——2
|
3
或
1——2——3
这两种构造结果出现的概率均为$50%$。
容易验证，按照这种方式构造出来的图一定是一棵树。
我们将顶点$1$定为树根。
给定$N$，求：
$(1)$树根的度数的期望值是多少？
$(2)$树高（即树根到其余顶点的最大距离）的期望值是多少？
$(3)$树叶（即度数为$1$的顶点）所占比例的期望值是多少？
页:
[1]