Content deleted Content added
Line 5:
== Random graph models ==
A random graph is obtained by starting with a set of ''n'' isolated vertices and adding successive edges between them at random. The aim of the study in this field is to determine at what stage a particular property of the graph is likely to arise.<ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref> Different '''random graph models''' produce different [[probability distribution]]s on graphs. Most commonly studied is the one proposed by [[Edgar Gilbert]], denoted ''G''(''n'',''p''), in which every possible edge occurs independently with probability 0 < ''p'' < 1. The probability of obtaining ''any one particular'' random graph with ''m'' edges is <math>p^m (1-p)^{N-m}</math> with the notation <math>N = \tbinom{
A closely related model, the [[Erdős–Rényi model]] denoted ''G''(''n'',''M''), assigns equal probability to all graphs with exactly ''M'' edges. With 0 ≤ ''M'' ≤ ''N'', ''G''(''n'',''p'') has <math>\tbinom{N}{M}</math> elements and every element occurs with probability <math>1/\tbinom{N}{M}</math>.<ref name = "Random Graphs2" /> The latter model can be viewed as a snapshot at a particular time (''M'') of the '''random graph process''' <math>\tilde{G}_n</math>, which is a [[stochastic process]] that starts with ''n'' vertices and no edges, and at each step adds one new edge chosen uniformly from the set of missing edges.
| |||