Traveling Salesman Problem (and Hamilton circuits) review

Which of the following is a Hamilton circuit of the graph?

• ABCDEFGA
• ACBEGFDA
• CBGEDFAC
• CEGBADFC

List a path from vertex D to vertex G

• DAFCEBG
• DFACEBG
• DECAFBG
• DCBAFEG

True or false: With Hamilton circuits, every edge must be used. With Euler circuits, every vertex must be used.

• True
• False

What is the cost using Nearest Neighbor (Go Cheap) starting with vertex A?

• 63
• 58
• 55
• 52

Find a Hamilton circuit from D using the Nearest Neighbor Alogrithm.

• DAEBCD
• DBEACD
• DABECD
• DCABED

How would you rewrite the circuit AEDBCA where B is the starting vertex?

• BEDCAB
• BCAEDB
• BACEDB
• BADECB

Using the Brute Force method (Exhaustive Search), find the optimal route.

• ACDBA
• ABCDA
• ABDCA
• ACBDA

Use the nearest-neighbor algorithm to find a Hamilton Circuit starting at E. 

• E, A, C, D, B, E
• E, D, C, A, B, E
• E, D, C, B, A, E
• E, D, A, B, C, E

Use the nearest-neighbor algorithm to find a Hamilton Circuit starting at B. 

• B, E, C, D, A, B
• B, A, C, E, D, B
• B, A, D, E, C, B
• B, A, D, C, E, B

Use the nearest-neighbor algorithm to find a Hamilton Circuit starting at A. What is its weight?

• 11
• 9.9
• 10
• 10.5