Course 2 Unit 6 - Network Optimization
©2008

This unit in the discrete mathematics strand follows a unit in Course 1 on vertex-edge graphs, and a unit in Course 2 on matrices. (See the descriptions of Course 1 Units and Course 2 Units.) The study of discrete mathematics helps develop three important general skills: mathematical modeling, algorithmic problem solving, and optimization. This unit continues the development of all three of these skills with an emphasis on optimizing networks. Students will refine their optimization skills as they find minimum spanning trees, shortest Hamilton circuits, and longest paths that determine earliest finish time for large projects. They will further develop the skill of algorithmic problem solving as they carefully design, use, and analyze algorithms for optimizing networks. Students gain more experience with mathematical modeling as they model and solve problems using vertex-edge graphs.

Unit Overview
In this unit of Core-Plus Mathematics, students continue their study of vertex-edge graphs. Vertex-edge graphs are also known simply as graphs, particularly in college courses, or as networks. The formal study of vertex-edge graphs is called graph theory. In the Vertex-Edge Graphs unit in Course 1, students learned about Euler paths, adjacency matrices for graphs, and vertex coloring. In Matrix Methods, they encountered digraphs and learned more about adjacency matrices. In Network Optimization, students will study several more fundamental topics in graph theory—minimum spanning trees, Hamilton paths, the Traveling Salesperson Problem (TSP), and project scheduling using critical paths (also called the Program Evaluation and Review Technique, PERT, or the Critical Path Method, CPM).
     Vertex-edge graphs are part of geometry since they are geometric diagrams consisting of vertices and edges; although in contrast to most high school geometry, size and shape are not essential features of these geometric objects. Rather, it is the connections among vertices as shown by the edges that is essential. Vertex-edge graphs are also part of discrete mathematics, which includes iteration and recursion, combinatorics, the mathematics of democratic decision making, and information processing.

Sample Overview
The sample material for this unit is the "Looking Back" lesson for the unit. Each unit in Core-Plus Mathematics includes a final lesson designed to help students review and organize their thinking related to the mathematical concepts learned in the unit.

Instructional Design
Throughout the curriculum, interesting problem contexts serve as the foundation for instruction. As lessons unfold around these problem situations, classroom instruction tends to follow a four-phase cycle of classroom activities—Launch, Explore, Share and Summarize, and Apply. This instructional model is elaborated under Instructional Design.

View Sample Material
You will need the free Adobe Acrobat Reader software to view and print the sample material.

How the Discrete Mathematics Strand Continues
In Course 3 Unit 1, Reasoning and Proof, students will consider and develop proofs from discrete mathematics. In Unit 7, Recursion and Iteration, students study iteration and recursion as tools to model and analyze sequential change in real-world contexts, including compound interest and population growth; arithmetic, geometric, and other sequences; arithmetic and geometric series; finite differences; linear and nonlinear recurrence relations; and function iteration, including graphical iteration and fixed points.
     In Course 4: Preparation for Calculus Unit 8, Counting Methods and Induction, students study the following topics: systematic listing and counting, counting trees, the Multiplication Principle of Counting, Addition Principle of Counting, combinations, permutations, selections with repetition; the binomial theorem, Pascal's triangle, combinatorial reasoning; the general multiplication rule for probability; the Principle of Mathematical Induction; and proof using the Least Number Principle. (See the CPMP Courses 1-4 descriptions.)