Home
Syllabus
Classwork
Due Friday, March 6, at 4pm. Worth 30 points. Submit by uploading RandomGraph.java to Sauron [Instructions], and submit paper copies of your graphs to my office. You may choose to work with a classmate on this assignment; if you do so, you should submit a single solution together.
Many computer scientists and mathematicians study random graphs. The most commonly studied type of random graph is the following: Given an integer n and a probability p, we generate a graph randomly by creating n vertices and connecting each pair of vertices (u, v) with the same probability p. For example, given 3 vertices a, b, and c with a 50% probability, we'd flip a coin to decide whether to connect a and b; then we'd flip a coin to decide whether to connect a and c; and then we'd flip a coin to decide whether to connect b and c. One of eight possible graphs will result, each with equal probability.
A component of a graph is a subset of the vertices that are all connected to one another but connected to no other vertices. And we define the diameter of a graph to be the maximum distance between any two vertices within the same component. It's easy enough to count the components and determine the diameter for each of our 3-vertex graphs; in the below table, we've classified these graphs according to the number of edges, since it happens for 3-vertex graphs that any two graphs with the same number of edges are symmetric.
Statistics for 3-vertex graphs # edges # components diameter 0 3 0 (There is one 0-edge graph.) 1 2 1 (There are three 1-edge graphs.) 2 1 2 (There are three 2-edge graphs.) 3 1 1 (There is one 3-edge graph.)
In this assignment you are to write a program that receives two values n and p (either from the command line or the keyboard) and computes two statistics for random graphs under those parameters:
What is the expected number of components? Using 3 for n and 0.5 for p, we already know that all 8 possible graphs are equally likely, and so we can average the number of components in each graph to determine that the expected number of components would be 13/8 = 1.625.
What is the expected diameter of components? Using 3 for n and 0.5 for p, we already know that all 8 possible graphs are equally likely, and so we can average the diameter of each graph to determine that the expected diameter would be 10/8 = 1.25.
For reasonably large values of n, you cannot hope to actually generate all possible graphs and average as above. Instead, your program will just do sampling: You can generate, say, 100 random graphs, compute the number of components and diameter of each, and then report the average. You should use the UndirectedGraph class that I've developed.
After doing this, you should use your program to create two graphs. Of course, your program will just generate data; you'll want to use a program such as OpenOffice Calc to create the graphs that you will turn in to me.
The first graph will have p on the x-axis and the expected number of components on the y-axis; it should have one curve indicating how the expected number of components changes with p when n is 9, another for when n is 36, and another for when n is 144.
The second graph will do the same but with expected diameter on the y-axis.