Definitions Flashcards
What is meant by an unbalanced transportation problem?
Means that the supply is not equal to the demand.
What is meant by a degenerate solution to a transportation problem?
Means that the number of occupied cells is not equal to the number of rows + number of columns -1.
What is a walk?
A finite sequence of edges such that the end vertex of one edge is the start vertex of the next.
What is a tour?
A walk which visits every vertex, returning to the starting vertex.
Describe the classical travelling salesman problem.
This is where you visit each vertex only once before returning to the starting vertex.
Describe the practical travelling salesman problem.
This is where you visit each point at least once before returning to the starting vertex.
What is a slack variable?
A slack variable represents the spare capacity in a constraint.
What is meant by a zero sum game?
The sum of the total gain for both players is 0.
What is meant by the saddle point in a game?
In a game which has a stable solution, the saddle point is the location of where the row maximin = the column minimax.
Describe what is meant by domination in a zero sum game?
If every value of a row (or column) is a better option than the corresponding row (or column) then the better option dominates. The dominated row (or column) can be deleted from the game.
What is meant by a capacitated, directed network?
A network in which each arc has a weight which represents the capacity of that arc in a given direction.
What is the feasibility condition in a flow network?
The condition is that the flow along an arc must not exceed the capacity of the arc.
What is the conservation condition in a flow network?
The condition is that the total flow into a vertex = total flow out of a vertex.
What is meant by a cut?
This is a set of arcs whose removal splits the network into two parts one containing the source, the other the sink.
Describe what is meant by a minimum cut?
A cut consisting of saturated arcs into the cut and empty arcs out of the cut.
