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