Search topics

Search
1 of 8 0-day streak

Hamiltonian paths and cycles

DIFFICULTYintrostandardchallengeexam
QUESTION TYPEMix of allChange
path; not asked; compact pathpath; not asked; meshed pathNOWMix of allRecommended
Question 1 of 8

No calculator

Consider the network of paths between festival locations. Each labelled point represents a festival location, and each line represents a direct path

Unweighted network with no loops or parallel edges. Vertices in listed order: [Pavilion | Entry | Workshop | Food Court | Market]. Full edge list: Entry–Workshop; Market–Food Court; Workshop–Market; Entry–Market; Workshop–Pavilion; Pavilion–Food Court.PavilionEntryWorkshopFood CourtMarket
(a)1 mark

Which option visits the graph's vertices as a Hamiltonian path?

(b)1 mark

How many edges does the correct route use?