A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Hamiltonian Cycles

FM Hamiltonian Cycles

2.3 Hamiltonian Paths and Cycles

Note: if you cannot remember the concepts of walks, paths and cycles, revise notes for 2.1 Introduction to Walks.

Hamiltonian Paths

  • 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.

Example

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