Euler & Hamilton 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

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

• ACDBA
• ABCDA
• ABDCA
• ACBDA

Tags

CCSS.HSA.REI.C.6

Tracing all edges on a figure without picking up your pencil and repeating and starting and stopping in the same spot

• Euler Circuit
• Euler Path

Tracing all edges on a figure without picking up your pencil or repeating and starting and stopping at different spots

• Euler Circuit
• Euler Path