ランダム・グラフ

らんだむ・ぐらふ random graph

一般的に， Erd\"{o}sによって導入されたランダム・グラフを指すことが多い． これは，$n$点からなる点集合における二点の組それぞれに対して， その間に確率$p$で辺を張ることで生成されるグラフのことである． ランダム・グラフの次数分布はポアソン分布に従い， クラスタ係数は点数$n$の増加にしたがって0に収束する． 平均点間距離は構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle O(\log n)} である．