黑客排名谜题。随机图需要多少条边才能连通

这是 Interviewstreet 谜题：

我们有一个包含 N 个城市的国家。每天我们选择两个城市之间没有道路，并在它们之间修建一条道路。我们以相同的概率选择每对不相邻的城市。令 X 为我们获得连接国家/地区之前的天数。 X 的期望值是多少？输出答案的整数部分。

他们真正要问的是随机图 G(n, m) 需要多少条边 m（平均）才能连接起来。

在编写了一个实际执行实验的程序后，我想出了这个通过 9/10 测试的“解决方案”

$f = fopen('php://stdin', 'r');
$n = intval(fgets($f));
echo round(1.25 * $n * log($n, 10));

那么可以用一个公式来解决吗？查找随机图连通性可能性的正确方法是什么？

你应该看看鄂尔多斯和仁义1960年的经典论文，题为《论随机图的演化》 http://www.renyi.hu/~p_erdos/1960-10.pdf。它包含组件数量、最大组件大小等的完整概率范围。

这里有一些数学设置可以帮助您入门。

Let G(n,m)是简单的随机图n顶点与m边缘。让X_k是添加的边数k连接的组件，直到有k-1连接的组件。例如，最初有n连接的组件，因此添加第一条边会导致n-1连接的组件所以X_n = 1。同样，第二条边也删除了一个组件（尽管这以两种方式之一发生），所以X_n-1 = 1以及。定义

X = X_n + X_n-1 + ... + X_2

目标是计算E(X)，期望值X。通过可加性，我们有

E(X) = E(X_n) + E(X_n-1) + ... + E(X_2) 

不难证明，当有边存在时，边添加的概率k组件减少组件数量的下限为(k-1)/(n-1). Since X_k是具有该数量给出的成​​功概率的随机变量，下界给出了期望的上限X_k:

E(X_k) <= (n-1)/(k-1)

结合起来，我们得到一个渐近上限E(X) by n log n.

通过更多的工作和鄂尔多斯-仁义论文中的一些提示，您可能可以推导出一个精确的公式。