Hackerrank谜题。一个随机图需要多少条边才能变得连通？

Question

这是一个来自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));

那么这可以用一个公式来解决吗？如何正确地找到随机图的连通性可能性？

- Evgeny

---

我该如何理解这句话：“我们选择两个城市，使它们之间没有道路”？假设A-B之间有一条道路，B-C之间也有一条道路，那么算法是否可能选择A-C之间的道路？ - Marsellus Wallace

是的，如果只有三个城市（A、B和C），那么唯一没有道路的剩余城市对是A-C。但是在这种情况下，整个国家已经通过仅有的两条道路连接起来了。 - Evgeny

其实，我不再确定了。在这个上下文中，“nonadjacent”是什么意思？是指“两个城市之间没有道路”的意思吗？因为这通常不是这个词的意思。问题也没有涉及到如果A被B完全包围，如何在A和C之间建立道路。如果这是不可能的——在物理上不可能——那么答案就不仅仅取决于N。 - user743382

@hvd，你的第一次解释完全正确。 - Evgeny

当没有道路（A，B）时，A和B是不相邻的。 - Evgeny

Answer 1

你应该查看Erdos和Renyi在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

目标是计算X的期望值E(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。

再经过一些工作并从Erdos-Renyi论文中获取一些提示，您可能可以推导出一个精确的公式。

- PengOne

---

我不确定你所说的“最初有n个连通分量”的意思。难道不是我们不知道有多少个顶点是相连的吗？添加一条边怎么会导致更少的连通分量呢？我是否混淆了你所说的连通分量的含义。我认为它指的是相连的顶点。 - Scott

Answer 2

OP的解决方案非常好，公式稍作修改即可始终通过。

$f = fopen('php://stdin', 'r');   
$n = intval(fgets($f));  
echo round(1.249 * $n * log($n, 10));// constant factor is changed

- Blazer