Further Methods

There are many other network algorithms and concepts that are not assessed in this standard.

In some cases, the concepts are no more difficult than those assessed in standard 91260; the standard is just clearly defined as only containing three key methods.

Nothing in this topic should be assessed; it is here only for interest.

Hamiltonian paths

In much the same way that Euler described a tour of all the edges in a network, we could consider finding a tour of all the nodes; a path which visits every node exactly once. Such a tour is named after Sir William Rowan Hamilton because of a puzzle he made in 1857, despite Thomas Kirkman publishing the same idea in 1856. It turns out that although there is a very straightforward way to determine whether or not a network has an Euler path, no simple rule for "is there a Hamiltonian path?" is known to exist. A Hamiltonian circuit is a Hamiltonian path that starts and ends at the same node.

The problem is what computer scientists call "NP-complete"; in general, nothing other than an exhaustive search can find (or show the lack of) a Hamiltonian path or circuit.

Travelling Salesman problem

This problem is an extension of Hamiltonian paths and circuit. It asks for the shortest Hamiltonian path (or circuit); the shortest route for a salesman to visit all of the towns in a region exactly once. This is an intractably difficult problem, with no algorithm known. Any question which asks some variant of "visit each location" is some form of Hamiltonian path or Travelling Salesman route search. For very small networks, trying all possible tours of the nodes and choosing the shortest can be feasible.

The problem is NP-complete; no algorithm for solving the Travelling Salesman problem exists.

Maximum Spanning Tree

As the name suggests, this is still a spanning tree, but chosen to maximise the total weight. Not inherently more difficult that minimum spanning tree (instead of removing the largest weight edge from circuits, remove the smallest), but of less real-world use.

Directed Edges

We can think of having directions on the edges in a network; travel is only allowed in that direction. This could be a one-way road network, or an airline that has flights Auckland>Christchurch>Sydney>Auckland in a loop but not in the other direction. The whole network for a task in this standard would not have directed edges; but a question requiring extended abstract thinking might ask what would happen if a certain edge could only be traveled in one direction.

Planar graphs

A network (typically called a graph in this branch of mathematics) is planar if it can be drawn with none of its edges crossing. With networks that represent roads between towns, this is what we expect. If the edges of a network were flights between airports, then it is possible that edges would have to cross. The smallest graph that is not planar has five nodes, and all of the nodes connected to each other (ten different edges).

Alternative terminology

Nodes can be called vertices (singular vertex) or points. Edges can be called arcs or lines. Circuits can be called cycles. Paths can be called walks. There's no right or wrong, and different resources use different synonyms, largely depending on the author's preference. Keep an eye out for unexpected terminology, and be sure you know what it means.