黑客难题。一个随机图需要多少条边连接 [英] Hackerrank puzzle. How many edges needed for a random graph to become connected

问题描述

这是Interviewstreet拼图：

我们有一个包含N个城市的国家。我们每天选择2座城市，这样两座城市之间就没有道路，并在它们之间建立一条道路。我们以相等的概率选择每对不相邻的城市。设X是我们获得互联国家之前的天数。 X的期望值是多少？输出答案的整数部分。

他们真正要求的是随机数需要多少个边m（平均）图G（n，m）成为连接。

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

  $ f = fopen（'php：// stdin'，'r'）; 
 $ n = intval（fgets（$ f））; 
 echo round（1.25 * $ n * log（$ n，10））; 
  

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

解决方案

您应该查看Erdos和Renyi的经典论文自1960年起，题为关于随机图的演变。它包含了组件数量，最大组件大小等的完全概率界限。

这里有一些数学设置可以帮助你开始。

>

令 G（n，m）为 n 具有 m 边的顶点。令 X_k 为在 k 连通分量之前添加的边数，直到存在 k -1 连接的组件。例如，最初有 n 连接组件，因此将第一个边添加到 n-1 连接组件中， code> X_n = 1 。同样，第二个边也会删除一个组件（虽然这是以两种方式之一发生的），所以 X_n-1 = 1 也是如此。定义

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

目标是计算 E（X），期望值 X 。通过可加性，我们有：
$ b $ pre $ E（X）= E（X_n）+ E（X_n-1）+ ... + E（X_2）


不难证明，当边 k 组件减少了组件的数量，其下限为（k-1）/（n-1）。因为 X_k 是随机变量，其成功概率由该量给出，所以下限给出 X_k
$ p $ E（X_k）<=（n-1）/（k-1）


结合这个，我们得到 E（X）由 n log n 。



通过鄂尔多斯 - 仁义报纸的一些工作和一些提示，您可以推断出一个确切的公式。

This is Interviewstreet puzzle:

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.

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.

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?

解决方案

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.

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

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) 

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)

Combining this, we get an asymptotic upper bound for E(X) by n log n.

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

这篇关于黑客难题。一个随机图需要多少条边连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！