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

The diagram shows routes between museum galleries. Each labelled point represents a gallery, and each line represents a direct passage

Unweighted network with no loops or parallel edges. Vertices in listed order: [Ceramics | History | Portraits | Design | Atrium]. Full edge list: History–Design; Design–Atrium; Ceramics–Atrium; Ceramics–Design; Portraits–Atrium; Portraits–History; Portraits–Design.CeramicsHistoryPortraitsDesignAtrium
(a)1 mark

Select the sequence that forms a Hamiltonian path

(b)1 mark

How many distinct vertices does the correct route visit?