Random graph

Realization of the Gilbert graph ${\displaystyle G(20;\;0{,}1)}$

A random graph describes a graph in which the edges are generated randomly. Frequently used models of random graphs are:

• Gilbert graph :with a natural number, the number of nodes, and a probabilitydenotes the set of all graphs in which for each ordered pair of nodes, with, with the probability it isdetermined whether they are connected by an edge, and that regardless of the other edges. One then often investigates the probability with which the generated graphs have a certain property, e.g. B. whether they are connected. Another possibility is tospecify as afunction ofand thento examinethe behavior as it increases. ${\displaystyle G(n,p)}$ ${\displaystyle n\geq 1}$ ${\displaystyle 0\leq p\leq 1}$ ${\displaystyle (v_{1},v_{2})}$ ${\displaystyle v_{i}\leq n}$ ${\displaystyle p}$ ${\displaystyle p=p(n)}$ ${\displaystyle n}$ ${\displaystyle n}$

• Erdős - Rényi -Graph :with natural numbersanddenotes the set of all graphs with exactlynodes andedges. ${\displaystyle G(n,m)}$ ${\displaystyle n\geq 1}$ ${\displaystyle m\geq 0}$ ${\displaystyle n}$ ${\displaystyle m}$

• The nodes of the graph are distributed in the plane according to a predetermined probability distribution. If two nodes have a distance less than a given limit , they are connected by an edge. ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle f}$ ${\displaystyle v_{1},v_{2}}$ ${\displaystyle d}$

Questions

Important questions with random graphs are:

• Given a property and test for which or and from which graph size do all graphs have the property ? ${\displaystyle Q}$ ${\displaystyle p}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle Q}$

• Given a property , is the probability for against 1 or 0 for ? One then also says that almost all or almost no graphs fulfill the property . ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle n\rightarrow \infty }$ ${\displaystyle Q}$

Important results

By applying the probabilistic method to his random graph model, Paul Erdős proved the theorem: For every natural number there is a graph in which both the waist size (length of the shortest circle) and the chromatic number are greater than k. ${\displaystyle k}$

In the same random graph model it could be shown that isomorphism to any graph can be decided for almost all graphs in linear time.

literature

• Douglas B. West: Introduction to Graph Theory . Prentice Hall, Upper Saddle River, NJ 1996, ISBN 0-13-227828-6 .

Individual evidence

1. ↑ EN Gilbert: Random graphs , Annals of Mathematical Statistics, Volume 30, 1959, pp. 1141-1144
2. ↑ P. Erdős, A. Rényi: On Random Graphs I , Publ. Math. Debrecen 6, 1959, pp. 290-297
3. ^ Reinhard Diestel, Graphentheorie, Berlin, Heidelberg, New York: Springer, 3rd edition 2006, pp. 256ff.
4. ^ Babai, László, Paul Erdös, and Stanley M. Selkow. "Random graph isomorphism." Society for Industrial and Applied Mathematics Journal on Computing 9.3 (1980): 628-635. on-line