古典的なグラフ

http://iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2F%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E2%80%95%E5%9F%BA%E7%A4%8E%E3%81%8B%E3%82%89%E5%BF%9C%E7%94%A8%E3%81%BE%E3%81%A7%2F04.%20%E5%8F%A4%E5%85%B8%E7%9A%84%E3%81%AA%E3%82%B0%E3%83%A9%E3%83%95

• 完全グラフ
• 空間に埋め込まれた格子
• 木
• ランダムグラフ

ランダムグラフ

• エルデシュ・レニィーグラフ
  • 全頂点対について確率 p で枝を張る

$p$ による相転移

• 連結成分
  • $p < \frac1N$ → 最大連結成分 $O(\log N)$
  • $p = \frac1N$ → $O(N^\frac23)$
  • $p > \frac1N$ → $O(N)$
  • $p \geq \frac{\log N}N$ → 全体連結
• サイクル
  • $p=\frac1N$ → 最初のサイクル出現
• 木
  • $p \propto N^{-\frac{N'}{N'-1}}$ → 頂点数 $N'$ の木が最初に出現
• クリーク
  • $p \propto N^{-\frac{2}{N'-1}}$ → 頂点数 $N'$ のクリークが最初に出現

その他性質

• 次数分布：二項分布 → ポアソン分布
• $L \approx \frac{\log N}{\log \langle k \rangle}$
• $C = \frac{\langle k \rangle}{N - 1}$
• 長さ $l$ のサイクルの平均個数 $p^l \frac{N!}{(N-l)!(2l)!}$
• 隣接行列の固有値：ウィグナーの半円則