古典的なグラフ

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)!}$
  • 隣接行列の固有値:ウィグナーの半円則