Hamilton Paths and Circuits

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₉?

• 45
• 9!
• 8!
• 36

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

• 3628800
• 39916800
• 55
• 66

Tags

CCSS.HSS.CP.B.9

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

• ACDBA
• ABCDA
• ABDCA
• ACBDA

Tags

CCSS.HSA.REI.C.6