1

我有一个关于随机图的作业。我无法理解这个问题。任何人都可以向我澄清我应该做什么吗？

让N是一个正整数和p一个介于 0 和 1 之间的数字。(N, p)随机图是由以下过程生成的图：

绘制N顶点，分别表示1, 2, . . . , N为；对于每一对(u, v)不同的顶点，以概率p将这两个顶点与一条边连接起来。如果任意两个顶点之间存在路径，则称图是连通的。

在本实验中，您将编写代码来生成大型随机图并研究此类图的连通性。

我们将固定N为，500,000但让 p 变化{0.05, 0.10, 0.15, ..., 0.95}。对于每个 p 值，您需要创建 100 个(N, p)随机图。您需要开发一种方法（当然还要在您的程序中实现它）来确定图是否已连接。然后对于 p 的每个值，您需要计算M连接的随机图的数量，并研究M（反映随机图连接的概率）和之间的关系p。

4

1 回答 1

0

随机图是随机创建的图：

伪代码

for i := 1 to N
   for j := i+1 to N
       if bernoulli_distributed_with_param_p is true
           add undirected edge {i,j} to graph

该参数p只是两个给定顶点连接的概率。bernoulli_distributed_with_param_p在 C 中实现实际上非常简单：

// Returns 0 with probability (1-p)
int bernoulli_distributed(double p){
    return (p > ((double)rand())/RAND_MAX);
}

不要忘记您需要使用 初始化随机生成器srand。

于 2012-11-29T23:15:46.367 回答