Assignment 8

1.  The matrix below shows the mileage between five towns.  There are no roads connecting some pairs of towns.

	A	B	C	D	E
A	-	25	30	-	20
B	25	-	-	50	35
C	30	-	-	35	25
D	-	50	35	-	30
E	20	35	25	30	-

a) Represent the information in the matrix with a vertex-edge graph

b) List the vertices for all the Hamiltonian circuits that begin at A.  Do NOT use reverse order circuits.

c) Record the total length of each circuit you found in Part b

d) Would you get different lengths for the circuits in part c if the starting vertex were B?  Explain.

e) What is the solution to the Traveling Salesperson Problem for the graph in Part a?

f) Explain the difference between finding a minimal spanning tree for a vertex-edge graph and solving the Traveling Salesperson Problem

g) Give an example of a question about the five towns in Part a that could be answered by finding a minimal spanning tree for the graph.