Course 2, Unit 5 - Network Optimization

Summary
Need summary here, like that provided for Course 2 Units 1-4.

Key Ideas from Course 2, Unit 5

  • Optimization: The process of looking for the best solution, whether this is a shortest path, a minimal spanning tree, or a minimal circuit.
  • Tree: A vertex edge graph which has no circuits. (See Course 1 Unit 4 for introductory work with graph models.) For example:





  • Minimal spanning tree: A subset of a vertex edge 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 minimal spanning tree. (See page 323 Activity 7 for KruskalŐs algorithm, and page 324 Activity 9 for the nearest-neighbor algorithm.) For example:



  • Traveling salesperson problem: A particular problem represented by a vertex edge 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 optimal solution. Brute force methods are impractical if more than a few vertices are involved.
  • Best-edge algorithm: One best-edge 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 previously-added edges. The result is a minimal spanning tree.
  • Brute force method: This is another algorithm for solving optimizing problems. Basically, all solutions are found and then the best is chosen. Obviously this is not practical in many situations.
  • Hamiltonian 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.
  • Shortest path lengths: A path starts at one vertex, visits all other vertices without repeating an edge, and ends at another vertex. The shortest path has the shortest total edge lengths. This is different from a minimal spanning tree in that circuits may be included.
Copyright 2008 Core-Plus Mathematics Project. All rights reserved.