Home      d2definitions
D2 Definitions

Below are the definitions for the Decision 2 Edexcel exam.

Travelling salesmen problem - is to find a route of minimum length that visits every vertex in an undirected network.
Classical - each vertex is visited only once.
Practical - a vertex may be revisited.

Walk - a finite sequence of edges such that the end vertex of one edge is the start vertex of the next edge.

Tour - a walk which visits every vertex and returns to the start vertex.

Zero-Sum Game - a game in which the sum of the losses of one player is the sum of the game of another player.

Bellman's Principle - any part of an optimal path is optimal.

Minimax route - the maximum length of the arcs used is as small as possible.

Maximin route - the minimum length of the arcs used is as a large as possible.

Cut - is a set of edges whose removal separates the network into two parts X and Y, where X contains at least the source and Y contains at least the sink.

Capacity of a Cut - is the sum of the capacities of those arcs in the cut which are directed from the source to the sink.