MA19.FM.19
Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.
Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.
UP:MA19.FM.19
Vocabulary
- Vertex coloring
- Matching techniques
- Conflict graphs
- Adjacent edges
- Adjacent vertices
- Odd wheel graph
- Proper coloring
Knowledge
Students know:
- Graphing procedures and properties.
Skills
Students are able to:
- Model application-based problems that may be solved using graph colorings.
- Color the edges or vertices of a graph using the least number of colors so that no two adjacent vertices or edges are colored the same.
- Interpret the coloring of the graph in terms of a solution for an application-based problem, such as scheduling committee meetings (vertex colorings) or class scheduling (edge-colorings).
- Identify structures in a graph that require a minimum number of colors for a proper coloring.
Understanding
Students understand that:
- -Techniques are used to minimize colors needed to color the vertices (edges) of a graph so that no two adjacent vertices (edges) are colored the same. -Real-world problems such as scheduling and conflict can be modeled with graphs and solved using the minimization of the number of colors.
Body
- Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.
Examples: Use graph-coloring techniques to color a map of the western states of the United States so that no adjacent states are the same color, determining the minimum number of colors needed and why no fewer colors may be used; use vertex colorings to determine the minimum number of zoo enclosures needed to house ten animals given their cohabitation constraints; use vertex colorings to develop a time table for scenarios such as scheduling club meetings or for housing hazardous chemicals that cannot all be safely stored together in warehouses.
