 |
 |
2 of 32 |  |
 |
 |
MIT
Random Graphs
l
Erdos-Renyi 1961
l
Graph G(p)
»
n
vertices
»
each edge present with probability
p
l
Connectivity threshold
»
connected w.h.p. when p > p
0
=(log
n)/n
»
connectivity k
w.h.p. when p = k/n >> p
0