ランダムグラフと巨大連結成分
各辺を確率 p でつなぐ。p が閾値 1/n を超えると巨大連結成分が突然出現します。
0.020
60
—
辺数 m
—
連結成分の数
—
最大成分のサイズ割合
—
平均次数 〈k〉 = p(n−1)
—
最大成分のサイズ割合 |LCC|/n と p の関係（紫の縦線 = 閾値 pc=1/n、赤点 = 現在の p）
頂点位置は固定。各辺は固定の乱数しきい値 wij を持ち、wij < p のときだけつながる。色が同じ頂点は同じ連結成分。赤＝最大連結成分(LCC)。
エルデシュ–レーニイ（Erdős–Rényi）モデル G(n, p) は、n 個の頂点のすべてのペアを独立に確率 p でつなぐランダムグラフです。
ここでは各潜在辺ごとに固定のしきい値 wij（0〜1 の乱数）を最初に一度だけ決め、スライダーの p に対して wij < p の辺だけを表示します。こうすると p を上げるほど辺が単調に増え、整合的に成長する様子が見えます。
p を 0 から少しずつ上げ、ばらばらの小さな断片が、ある瞬間に一気に巨大連結成分（giant component）へまとまる相転移を体感してください。
ここでは各潜在辺ごとに固定のしきい値 wij（0〜1 の乱数）を最初に一度だけ決め、スライダーの p に対して wij < p の辺だけを表示します。こうすると p を上げるほど辺が単調に増え、整合的に成長する様子が見えます。
p を 0 から少しずつ上げ、ばらばらの小さな断片が、ある瞬間に一気に巨大連結成分（giant component）へまとまる相転移を体感してください。
いま何が起きている？
ここがポイント
- p が小さい（〈k〉<1）と小さな断片ばかり ── 平均次数が 1 未満だと、連結成分はせいぜい O(log n) サイズの木にとどまります。
- p ≈ 1/n で相転移 ── 平均次数 〈k〉 = p(n−1) が 1 を超えるあたりで、全体の一定割合を占める巨大連結成分が突然出現します（パーコレーション転移）。
- p → 1 で完全グラフ ── すべての辺がつながり、全頂点が 1 つの成分（割合 1.0）になります。
- これはアルゴリズムでなく「性質」 ── 最短路や全域木の手順ではなく、ランダムグラフが示す確率的な相転移そのものを見ています。