10-15 Diameter

Recall the setup from the previous project:

1. Generate a random graph (“maze”) with 2000 vertices.
2. Add 100 random edges to your graph.

Diameter

The diameter of a graph is the maximum shortest distance between any two vertices.

• Draw two “nontrivial” example showing you can compute the diameter.

  • A 7 vertex graph where every vertex is within 3 of vertex 0 and the graph has a diameter of 6.
  • A 7 vertex graph where every vertex is within 3 of vertex 0 and the graph has a diameter of 3. (Check?)

• Write a function to compute the diameter of a graph.

Test your function using the 2000 vertex graph from earlier, before and after adding the random edges.

1. What diameters do you get?
2. Since the graphs are random, how much do the diameters change as you build different graphs?
3. How much do you expect the diameter of the graph change when you add in those random edges? (Answer experimentally.)

• ←Previous
Next→