Hamilton Circuits and Paths NWD

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

How many distinct Hamilton circuits are there in this complete graph? (There is a formula for this)

• 24
• 6
• 120
• 10

Tags

CCSS.HSS.CP.B.9

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

How many edges are there in the complete graph K₁₇?

• 160

• 153

• 120

• 136

How many distinct hamilton circuits are possible in the complete graph K₈?

• 362880

• 40,320

• 5040

• 720

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

• ACDBA
• ABCDA
• ABDCA
• ACBDA