Graphs are frequently used to model communications networks, and in this context the length of the shortest paths between vertices is of great importance.

In this assignment we will be assuming that the time to transmit a message from vertex x to vertex y is determined completely by the number of edges in the shortest path between x andy.

Given a connected graph G, it is natural to ask what the maximum vertex-to-vertex message time is.  In other words ...

Assuming that all messages are sent by the shortest possible paths, what is the maximum time for a message to get from one vertex to another?

To formalize this question, we can define some terms:

Let distance(x,y) = the number of edges in a shortest path between vertex x and vertex y

distance(x,y) = infinity if there is no path between x andy (this will never happen if G is connected)

Distance (x, x) = 0

Let diameter(G) = max(distance(x,y)|all vertices x andy in V)

Our question is now simpler to state:  Given a connected graph G, what is diameter(G)?

This is relatively easy to compute.  Recall that the Breadth-First-Search (BFS) algorithm, when started at a vertex v, reaches each vertex y using a minimum number of edges – i.e. BFS(v) finds the shortest paths from v to all other vertices. To find the diameter of G we run BFS on each vertex in turn, and keep track of the maximum distance of any other vertex from the start vertex each time.  Hint: if we start the BFS at vertex v, then distance(v, y) = 1+distance(v, y's parent in the BFS tree)

Your assignment is to carry out some simple experiments on the relationship between the number of edges and the diameter of a randomly generated connected graph. Please check the appendix for how to create such graphs.

Part 1: Implement the algorithm described above for generating random connected graphs.

To demonstrate correctness, generate a random connected tree on 8 vertices, print the adjacency lists and print the diameter of the tree, then add (about) 8 more edges, print the new adjacency lists for the graph, and print the diameter of the graph.

Part 2: Conduct the following experiment.

# choose a sample size k – it should probably be 10 or more, but you may find that for the # larger graphs the computation of the diameter is quite time-consuming – if so, using a

# smaller sample is acceptable

For n = 100, 200, 400, 800, 1600

for test = 1 to k:

generate a tree on n vertices

compute and record the diameter of the tree

add n randomly selected edges (either approximately or exactly)

compute and record the diameter of the graph

compute the average tree diameter and average graph diameter for your graphs with n vertices

Create a table or chart relating n to the average tree diameter and average graph diameter.

Can you discern a relationship?  How do the average diameters appear to grow as a function of n?

Part 3: Depth-First-Search (DFS) vs. Breadth-First-Search (BFS).

Building on the foundation established in Part 2, where you have already developed a methodology for generating random connected graphs, this part requires you to implement Depth-First Search (DFS) in additional to your previously implemented BFS and compare the traversaledge sums generated by two approaches.

During the traversal of the graph with each algorithm, compute the sum of the lengths of all visited edges (each edge has a length of 1 in this assignment). Note, for DFS, you should count the backward edges you visited too. What we ask for is not spanning tree of DFS.

Specifically, the algorithm is as follows:

# choose a sample size k – it should probably be 10 or more, but you may find that for the # larger graphs the computation of the diameter is quite time-consuming – if so, using a

# smaller sample is acceptable

For n = 100, 200, 400, 800, 1600