Use the following graph to answer parts a$-$d$.$

a$.$ Use the best edge algorithm to find the approximate least cost Hamilton circuit for the graph below.

Then, write your final answer starting with vertex $A.$

Circuit$)$:

Cost:

b$.$ Use the nearest neighbor algorithm, starting with vertex A$,$ to find the approximate least cost Hamilton

circuit. List both the order of the cities visited as well as the cost.

Circuit$)$:

Cost:

c$.$ Did you get the same answer using the nearest neighbor algorithm and best edge algorithm? Explain.

Which approximation algorithm produced the better solution?

d$.$ What is the only algorithm that guarantees the optimal solution? How many Hamilton circuits would

have to be generated to use this algorithm?