Random Graph
A random graph is a graph in which properties such as the number of graph vertices, graph
edges, and connections between them are determined in some random way. The graphs
illustrated above are random graphs on 10 vertices with edge probabilities distributed
uniformly in ![[0,1]](/National_Library/20161222123739im_/https://mathworld.wolfram.com/images/equations/RandomGraph/Inline1.gif)
.
Erdős and Rényi (1960) showed that for many monotone-increasing properties of random graphs, graphs of a size slightly less than a certain threshold are very
unlikely to have the property, whereas graphs with a few more graph
edges are almost certain to have it. This is known as a phase
transition (Janson et al. 2000, p. 103). Almost all graphs are connected
and nonplanar (Skiena 1990, p. 156).
The Wolfram Language command RandomGraph[
n, m
] gives a pseudorandom
graph with 
vertices and 
edges.
SEE ALSO: Graph,
Graph
Theory,
Phase Transition
REFERENCES:
Bollobás, B. Graph
Theory: An Introductory Course. New York: Springer-Verlag, 1979.
Bollobás, B. Random
Graphs. London: Academic Press, 1985.
Erdős, P. and Rényi, A. "On the Evolution of Random Graphs."
Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61, 1960.
Erdős, P. and Spencer, J. Probabilistic
Methods in Combinatorics. New York: Academic Press, 1974.
Janson, S.; Łuczak, T.; and Ruciński, A. Random
Graphs. New York: Wiley, 2000.
Kolchin, V. F. Random
Graphs. New York: Cambridge University Press, 1998.
Newman, M. E. J. Strogatz, S. H.; and Watts, D. J. "Random Graphs with Arbitrary Degree Distributions and Their Applications. Phys. Rev.
E 64, 026118, 2001.
Palmer, E. M. Graphical Evolution: An Introduction to the Theory of Random Graphs. New York: Wiley,
1985.
Skiena, S. "Random Graphs." Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 154-160, 1990.
Steele, J. M. "Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees." Prob. Eng. Inform.
Sci. 1, 47-59, 1987.
Referenced on Wolfram|Alpha:
Random Graph
CITE THIS AS:
Weisstein, Eric W. "Random Graph." From
MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RandomGraph.html
Contact the MathWorld Team
random graph
