ランダムグラフモデル

Question

ランダムグラフで特定の固定確率でエッジを追加すると言うと、実際にはどういう意味ですか？

たとえば、確率が0.5の場合、0.5+0.5 = 1であるため、グラフに2つのエッジを追加できることを意味します。

Answer 1

ランダムグラフ$ g（n、p）$を計算するとします。これは、各エッジが確率$ p。

確率$ p $のテールと確率でヘッドを与えるコインがあるとします$ 1-p。$

次に、あなたは$ {1、...、n } $をあなたのグラフの頂点セットにし、各ペアに対して$（i、j） in { {1、 ldots、n }を取ります 2} $を選択します。コインをひっくり返します。テールが来ると、グラフにエッジ$（i、j）$を追加します。

Answer 2

ランダム$ g（n、p）$モデルでは、$ binom {n} {2} $エッジのそれぞれが確率でグラフに追加されます$ p $ 独立して. 。つまり、任意の2つのエッジを考慮すると、両方が2p $ではなく確率$ p^2 $のグラフにあります。

Answer 3

正しいと言われていることに加えて、次のように$ 0 leq p leq 1 $でランダムグラフ$ g（n、p）$を作成できます。

一連の頂点$ v $と空のエッジ$ e $があると仮定します。各$ v $ in $ v $：各$ u $ in $ v $（$ u> v $は$ v $のノードの間の合計順序に関して）：均一な乱数$ r $を生成する場所$ r in [0,1] $。 if（$ r leq p $）は、Edge $（v、u）$および$（u、v）$ to $ e $を含めます。

これにより、ランダムグラフ$ g =（v、e）$が生成されます$ g（n、p）$ $ | v | = n $。ただし、これは指示されたグラフです。それを指示されたグラフにしたい場合は、その場合は定義に従わないため、グラフ$（v、u）$のみを追加します。