Exercise 5.21: (a) Let f (n) be the expected number of random edges that must be

added before an empty undirected graph with n vertices becomes connected. (Connectedness is deined in Exercise 5.19.) That is, suppose that we start with a graph on

n vertices with zero edges and then repeatedly add an edge, chosen uniformly at random from all edges not currently in the graph, until the graph becomes connected. If

Xn represents the number of edges added, then f (n) = E[Xn].

Find program to estimate f (n) for a given value of n. Your program should track

the connected components of the graph as you add edges until the graph becomes connected. You will probably want to use a disjoint set data structure, a topic covered in

standard undergraduate algorithms texts. You should try n = 100, 200, 300, 400, 500,

600, 700, 800, 900, and 1000. Repeat each experiment 100 times, and for each value of

n compute the average number of edges needed. Based on your experiments, suggest a

function h(n) that you think is a good estimate for f (n).

(b) Modify your program for the problem in part (a) so that it also keeps track of

isolated vertices. Let g(n) be the expected number of edges added before there are no

more isolated vertices. What seems to be the relationship between f (n) and g(n)?