11-16 Tree Diam

Problem set using DFS and/or BFS.
  1. What is the definition of a tree? (That is, what conditions on a graph cause it to be considered a tree?)
  2. The diameter of a graph is the maximum distance between any two vertices. For a general graph, a quadratic algorithm is needed. When a graph is known to be a tree, describe a potentially more efficient algorithm for finding its diameter. (Skeina, Exercise 5-19)
  3. Implement and test your algorithm.

Testing

You are going to implement some randomized testing of your algorithm. To do this, you need both:

  • A definitely correct (slow) algorithm for finding the diameter of a graph.
  • A new, fast algorithm (from above) for finding the diameter of a tree.

The method of testing:

  • Varying random graphs with 1-20 vertices.
  • Varying initial random number of edges (1 to number of vertices).
  • Add edges until the graph is connected to avoid testing unconnected graphs, which we do not care about. (Diameter would be infinite in this case.)
  • Compute the diameter with your slow algorithm.
  • Compute the diameter with your fast algorithm.
  • Compare and summarize results.

A summary of the results will include at least one picture of any example you find where the two algorithms give different answers.

Note: You should do two kinds of random testing - randomly producing any graph (as described above) and randomly producing a tree (use mazegen from the shortest distance assignment).

Challenge

Skiena, Exercise 5-13.