Scheduling Clubs

Learning Resource Type

Learning Activity

Overview

This is a practice problem for graph theory conflict mapping using coloring. Students are presented with a problem dealing with scheduling clubs and are asked to create a conflict map using google drawings. They will color the graph to determine the fewest club periods needed to avoid overlapping students.

Phase

During/Explore/Explain
Mathematics (2019) Grade(s): 09-12 - Applications of Finite Mathematics

MA19.FM.19

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

  1. 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.

Learning Objectives

The students will solve a scheduling problem by using a graph and color theory. 

Activity Details

  1. Direct students to the activity Scheduling Clubs.
  2. Instruct the students to follow and answer the prompts provided in the activity independently. 
  3. Provide a brief tutorial on how to use Google Drawings if necessary.
  4. The teacher should monitor students' progress as they work to create their graphs to identify problems or gaps in learning.

Assessment Strategies

Once the students share their graphs through Google Docs, the teacher will assess the student responses and address any misconceptions or gaps in learning.

Students could also share their work with a partner and have them critique each other's work.

Variation Tips

If Wi-Fi is not available the document can be printed and distributed to the class as a paper copy.

If there are not enough devices for the entire class students can work in pairs or groups to complete the activity.

Background / Preparation

The teacher will need to ensure the classroom has the following:

1) internet connection (WiFi).

2) classroom set of computers, iPads, or smart devices. (If allowed students can use their own personal devices.)

Prior to the lesson, the teacher should be familiar with Google Drawing and should share the document Scheduling Clubs with the class.

Prior to the lesson, the teacher may want to provide a short tutorial on creating graphs using Google Drawing.

ALSDE LOGO