Chapter 1
The links between vertices on a graph
What are edges?
A number assigned to an edge of a graph that can be thought of as a cost, distance, or time associated with that edge.
What is a weight?
A person, machine, robot, operating room, or runway with time that must be scheduled.
A point that two different lines share in common.
What is an intersection point?
Initial balance
What is principal?
The number of edges meeting at the vertex of a graph.
What is valence?
A graph in which every pair of vertices is joined by an edge.
What is a complete graph?
The minimum number of colors (labels) needed in any vertex coloring of a graph.
The set of all possible solutions to a set of inequalities.
What is the feasible region?
Interest that is paid on both the original principal and the accumulated interest.
What is compound interest?
Every pair of vertices on a graph has at least one path connecting the two vertices.
What is connected?
An algorithm for attempting to find the cheapest route by visiting the next vertex which can be reached most cheaply and that has not already been visited
An ordering of the collection of tasks to be scheduled for the purpose of attaining a particular scheduling goal (ex. minimizing completion time).
What is a priority list?
An equation used to find the maximum or minimum in a linear programming problem.
What is the objective function?
Adding edges that duplicate existing edges to a connected graph to make all valences even.
What is eulerizing the graph?
A connected graph with no circuits
What is a tree?
A heuristic algorithm for bin packing in which the next weight to be packed is placed in the lowest-numbered bin already opened into which it will fit.
What is first-fit?
This principle states that there is a corner point of the feasible region that yields the optimal solution.
What is the Corner Point Principle?
P=A/((1+r/m)^(mt)
What is the formula for the present value of compound interest?
The best-ranked solution when a problem has various solutions that can be ranked in preference order.
What is the optimal solution?
A directed graph that shows which tasks precede other tasks among the collection of tasks making up a job.
What is an order-requirement digraph?
An heuristic algorithm for bin packing in which the next weight to be packed is placed into the open bin with the largest amount of room remaining.
What is worst-fit?
An inequality in a linear programming problem that reflects the fact that no more of a resource can be used than what is available.
A=d[((1+r/m)^(mt)-1)/(r/m)]
What is the formula for the future value of an ordinary annuity?