Note: if you cannot remember the concepts of walks, paths and cycles, revise notes for 2.1 Introduction to Walks.
- A Hamiltonian path is a path which visits every vertex of a graph exactly once.
- Hamiltonian paths are useful for situations when every vertex must be visited but the route taken does not necessarily matter. For example, when a message must be sent to every individual in a communication network.
- There are no convenient methods (within the scope of Further Maths) for determining if a Hamiltonian path exists in a network and it must be determined through observation.
A company has 6 distribution centres, named centre A-F. A delivery driver must deliver the company’s product to each centre. To optimise time, the driver plots a Hamiltonian path between the centres: B-A-D-C-E-F, as shown below:Read More »2.3 Hamiltonian Paths and Cycles