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
