Course 2 Unit 6 - Network Optimization
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.
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).
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.
of the Unit
- Understand and apply minimum spanning trees, Hamilton circuits,
the Traveling Salesperson Problem, and critical paths (including
ideas from the Critical Path Method, CPM, which is also called
the Program Evaluation and Review Technique, PERT)
- Further develop skill in mathematical modeling by modeling
and solving problems with vertex-edge graphs
- Further develop skill in algorithmic problem solving by designing,
using, and analyzing systematic procedures for solving problems
involving vertex-edge graphs
- Further develop the ability to recognize, formulate, and
solve optimization problems, particularly network optimization
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.
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
You will need the
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