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
