「ランダム・グラフ」の版間の差分
ナビゲーションに移動
検索に移動
Sakasegawa (トーク | 投稿記録) (新しいページ: 'らんだむ・ぐらふ random graph 一般的に， Erd\"{o}sによって導入されたランダム・グラフを指すことが多い． これは，<math>n</math>点か...') |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 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>)である． | |
