Maximum Randomness

A lattice graph is highly ordered, but a random graph is its opposite: maximally random. To create a random graph, begin with n vertices and no edges. Consider every possible pairing of vertices. For each pair either draw an edge having probability p or do not draw an edge with a probability of 1 — p.

We can predict the outcome for our two extreme cases: If p = 0, our random graph is edgeless. If p = 1, our graph is a simple graph, or more specifically, a clique graph in which all pairs of vertices are adjacent to each other. Between these two extremes, we expect intervening graphs to have about pn2/2 edges. The Hungarian mathematicians, Paul Erdos and Alfred Renyi, studied the number of vertices, edges and their connections: all determined randomly. Most proofs about random graphs consider, "almost every" random graph to have a certain property. "Almost every" means that as a random graph grows larger and larger towards infinity, the probability of our certain property occuring anywhere in the graph approaches 1. So if the probability of having an edge p is greater than a certain threshold probability, then almost every random graph is connected. This statement is important. The Erdos-Renyi random graph can be made to be as dense or as sparse as we want it to be just by adjusting the edge probability p.

0 0

Post a comment