Random graph

A random graph indicates a graph where the edges are generated at random. Frequently used models of random graphs:

  • Gilbert graph: with a natural number and a probability denotes the set of all graphs, which is determined for each ordered pair of nodes with the probability that they are connected by an edge, and the other independently of the edges. We then examined frequently, the probability that the resulting graph has a certain property, such as whether they are contiguous. Another possibility is to specify a function of and then to investigate the behavior with increasing.
  • Erdős - Rényi graph: with natural numbers and denote the set of all graphs with exactly nodes and edges.
  • The nodes of the graph are distributed in the plane according to a given probability distribution. If two nodes have a distance smaller than a given limit, they are connected by an edge.

Issues

Important questions in random graphs:

  • Given a property and test for which or from which graphs and all graphs have the property size?
  • If a property that the probability of 1 or 0 to go for? We then say well, almost all or almost none graphs satisfy the property.

Important results

Some NP -hard problems can be answered efficiently with the help of random graphs. For example, graph isomorphism can be tested for in.

311315
de