Interviewstreet谜。多少边缘所需要的随机图形，成为连接 [英] Interviewstreet puzzle. How many edges needed for a random graph to become connected

问题描述

这是Interviewstreet谜：

This is Interviewstreet puzzle:

我们有一个包含n个城市的国家。每一天，我们选择2个城市，使得它们之间没有路，并建立它们之间的道路。我们选择每对不相邻城市的概率相同。设X是天数，我们得到一个连接国之前。什么是X的期望值？输出答案的整数部分。

We have a country containing N cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

他们真正问的是什么是需要的边缘m个（平均）的随机图G（N，M）成为连接。

What they are really asking is what number of edges m is needed (on average) for a random graph G(n, m) to become connected.

写一些实际进行的实验程序后，我想出了这个解决方案传递9/10测试

After writing a program that actually performed the experiment, I came up with this 'solution' that passes 9/10 tests

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

所以可以用一个公式来解决？什么是发现随机图连通的可能性的正确方法？

So can it be solved with a single formula? What is the right way of finding likelihood of connectedness of random graph?

推荐答案

您应该检查鄂尔多斯和仁义的经典论文从1960年有权的关于随机图的演变。它包含完整的概率界限多个组件，最大组件的大小等。

You should check out the classic paper of Erdos and Renyi from 1960 entitled "On the evolution of random graphs". It contains complete probabilistic bounds for number of components, size of the largest components, etc.

下面是一个位的数学设置以让你开始。

Here's a bit of the math set-up to get you started.

让 G（N，M）是对简单随机图 N 顶点 M 边缘。让 X_k 是加边的数量，同时也有 K 连接组件，直到有 K -1 连接组件。例如，最初有 N 连接的部件，因此将第一边缘结果 N-1这样<连接组件code> X_n = 1 。类似地，第二边缘也除去的成分（尽管这发生在两种方法之一），所以 X_n-1 = 1 为好。定义

Let G(n,m) be the simple random graph on n vertices with m edges. Let X_k be the number of edges added while there are k connected components until there are k-1 connected components. For example, initially there are n connected components, so adding the first edge results in n-1 connected components so X_n = 1. Similarly, the second edge also removes a component (though this happens in one of two ways) so X_n-1 = 1 as well. Define

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

我们的目标是计算 E（X），的X中的预期值。通过加，我们有

The goal is to compute E(X), the expected value of X. By additivity, we have

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

这不是太难表明概率边缘加入，同时也有 K 组件减少了元件数量有下限的（K-1）/（N-1）。由于 X_k 是与这一数额给予的成功概率随机变量，下界给出了一个上限 X_k ：

It's not too hard to show that the probability that an edge added while there are k components reduces the number of components has a lower bound of (k-1)/(n-1). Since X_k is the random variable with probability of success given by this amount, the lower bound gives an upper bound for the expectation of X_k:

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

结合这一点，我们得到一个渐近上限<$​​ C $ C> E（X）按 N日志ñ。

通过更多的工作，并从鄂尔多斯 - 仁义纸一些提示，你也许可以推断出一个精确的公式。

With a bit more work and some hints from the Erdos-Renyi paper, you can probably deduce an exact formula.

这篇关于Interviewstreet谜。多少边缘所需要的随机图形，成为连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！