Chapter 23, PROBLEM SET 23.5 #4

Do you need an answer to a question different from the above? Ask your question!

If for a complete graph (or one with very few edges missing), our data is an n Ã— n distance table (as in Prob. 13), show that the present algorithm [which is O(n^{2})] cannot easily be replaced by an algorithm of order less than O(n^{2}).

**Data from Prob. 13**

Find a shortest spanning tree in the complete graph of all possible 15 connections between the six cities given (distances by airplane, in miles, rounded). Can you think of a practical application of the result?

PROBLEM SET 23.2:

PROBLEM SET 23.4:

PROBLEM SET 23.5:

PROBLEM SET 23.6:

PROBLEM SET 23.7:

PROBLEM SET 23.8: