View source for Graph, random

A probabilistic model for the study of frequency characteristics of various graph parameters. A random graph is usually understood to mean a certain class of graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450001.png" /> with a given probability distribution. An arbitrary graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450002.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450003.png" /> is said to be a realization of the random graph. Any numerical characteristic (parameter) of a graph (cf. [[Graph, numerical characteristics of a|Graph, numerical characteristics of a]]) can be regarded as a random variable. The concept of a random graph is highly useful in modelling connection networks which are subject to certain random changes or of logical networks whose elements may assume defective states; in considering a picture of phase transformations in statistical physics; in studying various biological processes; in problems of minimization of a [[Boolean function|Boolean function]], etc. In several cases the concept of a random graph makes it possible to utilize probability theory as a tool in order to obtain asymptotic solutions of enumeration problems.

In a typical construction of a random graph, all realizations are obtained by applying to a non-random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450004.png" /> (most often a complete graph) a certain procedure for the removal of its edges; it is usually assumed in so doing that the removals of different edges are independent events, and that the removal of an edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450005.png" /> occurs with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450006.png" />. Such a construction of a random graph is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450007.png" />. Of greatest interest is the study of the various numerical connectivity characteristics of a random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450008.png" />, such as the number of connected components, the diameter, radius, the connectivity number, etc., which can be interpreted as characteristics of the reliability of the respective connection network or logical network. In such a case the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450009.png" /> characterizes the reliability of a connection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500010.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500011.png" /> is the probability of its leaving the system.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500012.png" /> be a complete graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500013.png" /> vertices and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500015.png" />. The random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500016.png" /> is connected, has diameter and radius equal to 2 and contains a Hamilton cycle (cf. [[Graph circuit|Graph circuit]]) with a probability which tends to one as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500017.png" /> tends to infinity. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500018.png" /> is a function of the number of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500019.png" />, then the probability of the random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500020.png" /> being connected depends on the closeness of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500021.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500022.png" />. More exactly, let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500023.png" /></td> </tr></table>

then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500024.png" /> tends to one as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500025.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500026.png" />; it tends to zero if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500027.png" />; it tends to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500028.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500029.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500030.png" /> is a constant. In the last-mentioned case the number of edges of the random graph is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500031.png" />.

The same random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500032.png" /> can also be regarded as the graph obtained from the non-random empty graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500033.png" /> vertices by randomly connecting its vertices by edges so that any pair of vertices has probability of being connected, independently of the others, equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500034.png" />. This mode of formation of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500035.png" /> is made dynamic if one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500038.png" /> being assigned the meaning of time. The situation is then as follows. At the initial moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500039.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500040.png" /> separate vertices. Then, as the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500041.png" /> increases, there appear non-trivial connected components, representing trees or connected graphs with one cycle and a small number of vertices. Next there appears one  "main"  component containing a number of vertices asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500042.png" /> (for large values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500043.png" />). The process is subsequently distinguished by growth of the main component and by decrease in the number of small components. Finally, at some moment of time, the graph becomes connected. This evolution of the random graph can be regarded as the model of the picture of phase transformations, where the main component plays the role of the liquid phase, while the part of the rarified phase is played by components with a small number of vertices.

There exist many other types of random graphs, e.g. those connected with trees (random trees), with one-place mappings of a finite set into itself (random mappings), and with subgraphs of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500044.png" />-dimensional unit cube (random Boolean functions).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E.F. Moore,   C.E. Shannon,   "Reliable circuits using less reliable relays, I,II"  ''J. Franklin Inst.'' , '''1'''  (1960)  pp. 109–148</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.E. Stepanov,  , ''Problems in Cybernetics. Proc. Sem. in comb. math.'' , Moscow  (1973)  pp. 164–185  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A. Sapozhenko,   "The geometric structure of almost all Boolean functions"  ''Probl. Kibernetiki'' , '''30'''  (1975)  pp. 227–261  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdös,   A. Renyi,   "On random graphs I"  ''Publ. Math. Debrecen'' , '''6'''  (1959)  pp. 290–297</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,   A. Renyi,   "On the evolution of random graphs"  ''Publ. Math. Inst. Hung. Acad. Sci.'' , '''5'''  (1960)  pp. 17–61</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  B. Bollobas,   "Graph theory and combinatorics" , Acad. Press  (1984)</TD></TR></table>