Hackerrank之谜.随机图连接所需的边数

Question

这是Interviewstreet难题:

我们有一个包含N个城市的国家.每天我们选择2个城市,这样他们之间就没有道路,并且在他们之间建立了一条道路.我们以相同的概率选择每对不相邻的城市.设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));

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

Answer 1

你应该看看1960年题为"关于随机图的演化"的鄂尔多斯和仁义的经典论文.它包含组件数量,最大组件大小等的完整概率界限.

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

我们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).由于X_k该数量给出了具有成功概率的随机变量,因此下限给出了期望值的上限X_k:

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

结合这一点,我们就得到一个渐近上限E(X)的n log n.

有了更多的工作和鄂尔多斯 - 仁义报纸的一些提示,你可以推断出一个确切的公式.