1

ランダムグラフに関する宿題があります。質問が理解できません。誰かが私に何をすべきかを明確にしてもらえますか?

は正Nの整数で、p0 から 1 の間の数値とします。(N, p)ランダム グラフは、次の手順で生成されるグラフです。

それぞれNで示される頂点を描画します。1, 2, . . . , N異なる頂点のすべてのペア(u, v)について、確率pで、2 つの頂点をエッジで接続します。任意の 2 つの頂点間にパスがある場合、グラフは接続されていると言われます。

このラボでは、大きなランダム グラフを生成するコードを記述し、そのようなグラフの接続性を調査します。

に固定Nします500,000が、p は で変化し{0.05, 0.10, 0.15, ..., 0.95}ます。(N, p)p の値ごとに、100 個のランダム グラフを作成する必要があります。グラフが接続されているかどうかを判断するには、メソッドを開発する (そしてもちろんプログラムに実装する) 必要があります。次に、p の値ごとに、接続されているランダム グラフの数を数え、(ランダム グラフが接続されている確率を反映する)Mと の間の関係を調査する必要があります。Mp

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は、与えられた 2 つの頂点が接続される確率です。bernoulli_distributed_with_param_pCで実装するのは実際には非常に簡単です：

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

で乱数発生器を初期化する必要があることを忘れないでくださいsrand。

于 2012-11-29T23:15:46.367 に答える