[Solved]: Random graph model

Problem Detail: 

When we say that in random graph we add an edge with a certain fixed probability, what do we actually mean?

For example if probability is 0.5, does that mean that we can just add two edges in a graph because 0.5+0.5=1.

Asked By : Xara

Answered By : Jernej

Suppose you wish to compute the random graph $G(n,p)$ that is the graph with $n$ vertices where each edge is added with probability $p.$

Suppose you have a coin that gives tails with probability $p$ and heads with probability $1-p.$

Then what you do you take $\{1,...,n\}$ to be the vertex set of your graph and for each pair $(i,j) \in { \{1,\ldots,n\} \choose 2}$ you flip your coin. If it comes tails you add the edge $(i,j)$ to your graph otherwise you don't.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7629