CSCI 2300 Lab 2, Fall 2017, due Sep 20

An Erdos-Renyi random graph G(n,p) is generated by two parameters

Problems

  1. Generating a random graph. Write a function to generate a random graph given n and p.
  2. Computing the size of the largest connected component. Given a graph G and a threshold t, write a function to test whether G contains a connected component of t vertices or more.
  3. Testing your algorithm on randomly generated graphs.
    • Let n = 40.
    • For each c in [0.2,3.0] with step size 0.2, let p=c/n, generate 500 random graphs G(n,p) using your function for step 1.
    • Use your function for step 2 to calculate the percentage of graphs (out of the 500 graphs with the same c) whose largest connected component has at least t=30 vertices.
    • Output: a graph where the x-axis is c and the y-axis is the percentage. As c increases, more and more graphs should have large components, since they have more and more edges.
    • Hint: The total number of graphs you should generate is 500*15---there are 15 different c's and for each c you should generate 500 graphs. Note that the percentage is calculated for each c.
  4. (Optional) Based on your findings, in a random graph of size 40 about how many others does each node need to have edges to, in order for most of the graph to become one connected component? Investigate the same question for other values of n: how large does c needs to be in order for most of the nodes in the graph to become connected with high probability?

Other hints

Show your plot and your code to your TA to receive credit.