MA19.FM.18

Mathematics (2019) Grade(s): 09-12 - Applications of Finite Mathematics

MA19.FM.18
Apply algorithms relating to minimum weight spanning trees, networks, flows, and Steiner trees.

Unpacked Content

Knowledge

Students know:

Graphing procedures and properties.

Skills

Students are able to:

Model a problem using flows in networks.
Use technology or other tools to construct Steiner points.
Apply minimum weight spanning tree algorithms.

Understanding

Students understand that:

A spanning tree of a graph is the smallest subgraph.
There are n-1 edges in a spanning tree of a graph with n vertices.
Various algorithms are efficient methods for finding minimum weight spanning trees of a graph and shortest paths in a graph.
Steiner points of a graph are vertices added to create a shortest spanning tree which connects the original vertices, using Euclidean distance as edge weights.
Steiner points have degree 3, and the 3 edges form angles of 120 degrees.

Vocabulary

Spanning tree
Minimum weight spanning tree
Network
Flow
Kruskal's algorithm
Prim's algorithm
Steiner tree
Steiner points

COS Examples

Example: traveling salesman problem

Design by Adaptive Theme