Review Vocabulary

Algorithm A step-by-step description of how to solve a problem. (p. 43)

Brute force method The method that solves the traveling salesman problem (TSP) by enumerating all the Hamiltonian circuits and then selecting the one with minimum cost. (p. 46)

Complete graph A graph in which every pair of vertices is joined by an edge. (p. 45)

Critical path The longest path in an order-requirement digraph. The length of this path gives the earliest completion time for all the tasks making up the job consisting of the tasks in the digraph. (p. 60)

Fundamental principle of counting A method for counting outcomes of multistage processes. (p. 45)

Greedy algorithm An approach for solving an optimization problem, where at each stage of the algorithm the best (or cheapest) action is taken. Unfortunately, greedy algorithms do not always lead to optimal solutions. (p. 48)

Hamiltonian circuit A circuit using distinct edges of a graph that starts and ends at a particular vertex of the graph and visits each vertex once and only once. A Hamiltonian circuit can start at any one of its vertices. (p. 40)

Heuristic algorithm A method of solving an optimization problem that is “fast” but does not guarantee an optimal answer to the problem. (p. 51)

Kruskal’s algorithm An algorithm developed by Joseph Kruskal (AT&T Research) that solves the minimum-cost spanning-tree problem by selecting edges in order of increasing cost, but in such a way that no edge forms a circuit with edges chosen earlier. It can be proved that this algorithm always produces an optimal solution. (p. 53)

Method of trees A visual method of carrying out the fundamental principle of counting. (p. 42)

Minimum-cost Hamiltonian circuit A Hamiltonian circuit in a graph with weights on the edges, for which the sum of the weights of the edges of the Hamiltonian circuit is as small as possible. (p. 42)

63

Minimum-cost spanning tree A spanning tree of a weighted connected graph having minimum cost. The cost of a tree is the sum of the weights on the edges of the tree. (p. 54)

Nearest-neighbor algorithm An algorithm for attempting to solve the TSP that begins at a “home” vertex and visits next that vertex not already visited that can be reached most cheaply. When all other vertices have been visited, the tour returns to home. This method may not give an optimal answer. (p. 48)

NP-complete problems A collection of problems, which includes the TSP, that appear to be very hard to solve quickly for an optimal solution. (p. 51)

Order-requirement digraph A directed graph that shows which tasks precede other tasks among the collection of tasks making up a job. (p. 58)

Sorted-edges algorithm An algorithm for attempting to solve the TSP where the edges added to the circuit being built up are selected in order of increasing cost, but no edge is chosen that would prevent a Hamiltonian circuit from forming. These edges must all be connected at the end, but not necessarily at earlier stages. The tour obtained may not have the lowest possible cost. (p. 49)

Spanning tree A subgraph of a connected graph that is a tree and includes all the vertices of the original graph. (p. 53)

Traveling salesman problem (TSP) The problem of finding a minimum-cost Hamiltonian circuit in a complete graph where each edge has been assigned a cost (or weight). (p. 47)

Tree A connected graph with no circuits. (pp. p. 42 p. 53)

Weight A number assigned to an edge of a graph that can be thought of as a cost, distance, or time associated with that edge. (p. 42)