A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Exploring and Travelling Problems

FM Exploring and Travelling Problems

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

2.2 Eulerian Trails and Circuits

Note: if you cannot remember the features of walks, trails and circuits, revise notes for 2.1 Introduction to Walks.

Eulerian Trails

  • A Eulerian trail is a trail which encompasses every edge of a graph.
  • A Eulerian trail will exist if the graph:
    • Is connected.
    • Has exactly two vertices with an odd degree.
    • Eulerian trails are useful in situations where every edge must be visited, for example when planning a mail route.
    • A Eulerian trail will start from one of the odd vertices.

Example

Read More »2.2 Eulerian Trails and Circuits

2.1 Introduction to Walks

Walks

  • A walk is a sequence of edges linking connected vertices in a graph.
  • Walks can have repeated vertices and edges.
  • Walks can be denoted in a written form by listing the vertices, in order, with a dash between each.
  • Walks are shown graphically as a continuous line along each relevant edge. Arrows are placed along the line to show direction.

Example

The walk A-C-D-A-C is shown in the below graph:

Connected Graph

Read More »2.1 Introduction to Walks