



EXAMPLE  
NONEXAMPLE 
Minimum spanning tree: a subset of a vertexedge graph which connects all vertices, without making any circuits and by minimizing total edge lengths. (Lengths might represent actual distances, cost, or time, etc.) There are algorithms for producing a minimum spanning tree. (See p. 404 Problem 8 for Kruskal's algorithm, and p. 404 Problem 10 for the nearestneighbor algorithm.) For example:
Traveling Salesperson Problem: a particular problem represented by a vertexedge graph, in which the goal is to create a circuit from the start point to every vertex, without repeating any vertex, minimizing the total edge lengths. There is no algorithm for producing an optimum solution. Brute force methods are impractical if more than a few vertices are involved.
Hamilton circuit: As with other circuits, the goal is to start at one vertex, and return to the same vertex, without repeating an edge, but with the additional condition that each vertex can only be visited once. (See p. 408.)
Bestedge algorithm: One bestedge algorithm is to start with just vertices then add the shortest edge that will not create a circuit, and repeat this process until it is not possible to add an edge without creating a circuit. A new edge added does not have to be connected to previouslyadded edges. The result is a minimal spanning tree. (See p. 409.)
Brute force method: This is another algorithm for solving optimizing problems. Basically, all solutions are found and then the best is chosen. This is not practical in many situations. (See p. 409.)
Scheduling large projects: Critical path analysis is used to optimally schedule large projects comprised of smaller tasks, such as a building construction project. The vertices represent tasks, and the edges represent times, a note is added to the edge to indicate these times. The vertices (tasks) are arranged in a parallel format, sequentially according to the prerequisites in the context. (See pp. 435442 and CPMPTools VertexEdge Graph software.)
Critical path: the path through the graph that gives enough time for all tasks of the project to be completed.
Earliest finish time: the total task time for all tasks on the critical path for the project.