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 roads between health centres. Each labelled point represents a health centre, and each line represents a direct road

Unweighted network with no loops or parallel edges. Vertices in listed order: [West | Central | South | North | Harbour]. Full edge list: Harbour–West; North–South; Central–North; West–Central; West–North; South–West.WestCentralSouthNorthHarbour
(a)1 mark

Select the sequence that forms a Hamiltonian path

(b)1 mark

How many edges does the correct route use?