「ランダム・グラフ」の版間の差分
ナビゲーションに移動
検索に移動
細 ("ランダム・グラフ" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 1行目: | 1行目: | ||
| − | らんだむ・ぐらふ | + | '''【 らんだむ・ぐらふ (random graph) 】''' |
| − | random graph | ||
一般的に， | 一般的に， | ||
| − | Erd | + | Erdösによって導入されたランダム・グラフを指すことが多い． |
| − | これは，<math>n</math> | + | これは， |
| + | <math>n</math>点からなる点集合における2点の組それぞれに対して， | ||
その間に確率<math>p</math>で辺を張ることで生成されるグラフのことである． | その間に確率<math>p</math>で辺を張ることで生成されるグラフのことである． | ||
| − | + | ランダム・グラフの次数分布は[[ポアソン分布]]に従い， | |
| − | + | [[クラスタ係数]]は点数<math>n</math>の増加にしたがって0に収束する． | |
| − | + | 平均点間距離はO(<math>\log n</math>)である． | |
