Checkpoint
- Course 1, Unit 4
Graph Models
In each unit, there is a final lesson and Checkpoint that helps students
summarize the key ideas in the unit. The final Checkpoint will generally
be discussed in class, with the teacher facilitating the summarizing,
and students making notes in their Math Toolkits
(teachers may just refer to this as "notes") of any points they need
to remember, adding illustrative examples as needed. If your student
is
having difficulty
with any investigation
in this unit,
this Checkpoint and the accompanying answers may help you recall the
concepts involved, and give you the big picture of what the entire unit
is about.
If your student has completed the unit, then a version of this should
be in his or her notes or toolkit.
Possible Responses to Unit Summary Checkpoint
| The words in bold represent vocabulary and concepts
that students should have mastered in this unit. |
| a. |
For each of the problems in this lesson:
- Which graph model did you use?
- What did the vertices and edges represent?
- Explain why you chose the graph model you used?
- Office Complex. The goal here is to determine a path
that will allow the security guard to pass through each door
with the minimum number of repetitions. You can represent
this problem with a vertex-edge graph by letting the vertices
represent the rooms, and connecting two vertices with
an edge if the rooms they represent are connected by a
door. Then the ideal solution is to find a path that uses each door
(edge)
exactly once, without repetition, and returns to the starting
position. In graph terms, this means to find an Euler circuit.
Students have learned that a graph has an
Euler circuit if each vertex is touched by an even number
of edges (every vertex has even degree).
This makes sense if you think about arriving and departing
from each vertex. Since all vertices have even degree, every
time you come into a vertex, you are also able to leave the
vertex (since otherwise there would be an odd number of edge-touchings,
that is, an odd degree). Thus, you can create a route that
keeps moving through the graph until you eventually get back
to the start. (Note that this argument does not completely
prove the theorem, but it gives the general idea of why the
theorem is true.)
- Garbage Collector. This is a problem that involves conflict,
which indicates the possibility of using vertex coloring
to solve the problem. To do so, first figure out what the
conflict is, and this will determine what the vertices, edges,
and colors should represent. In this case, you don't want
to visit the same site more than once on a given day, which
can only happen if a site is on more than one route. Thus,
two routes are potentially "in conflict" if they contain a
common site. To avoid the conflict, two such routes must be
scheduled on different days so the common site won't be visited
twice in one day. Thus, let the routes be the vertices and
connect two vertices with an edge if they are "in conflict"
(i.e., if the routes they represent share a common site).
Color each vertex to show on which day of the week the route
is scheduled. Avoid conflicts by using different colors for
vertices that are connected by an edge. The goal is to use
the fewest colors, and thus schedule all the routes in the
fewest number of days.
- Traffic Lights. This is another problem involving conflict,
so look for a solution using vertex coloring. In this case,
two streams of traffic may be in conflict. That is, accidents
could occur if the two traffic streams have a green light
at the same time. Thus, let the streams of traffic be the
vertices, connect two vertices with an edge if the two streams
of traffic are in conflict, and assign different green light
cycles to conflicting traffic streams (assign different colors
to vertices connected by an edge). Then you can find the fewest
number of green light cycles needed to safely accommodate
all the traffic streams by coloring the vertices of the graph
with the fewest number of colors.
- School Newspaper. The key relationship here is not conflict,
as in the above problems, but rather prerequisites.
Some tasks are prerequisites for others, in which case one
task has to be done before the other, while other tasks
can
be done at the same time. The goal is figure out how all
the tasks in the project can be finished in the least total
amount
of time. Let the tasks be the vertices and connect two vertices
with an arrow if one is an immediate prerequisite of the
other.
This creates a digraph, that is, a graph with directed
edges (i.e., arrows). Each vertex is given a weight,
which is the amount of time required to complete that individual
task. The goal is to find a longest path through the graph.
You need a longest path to ensure that there is just enough
time to complete all the tasks. So the length of a longest
path will give the least amount of time needed to finish
all
the tasks in the whole project. (A longest path is called
a
critical path, since all the tasks on it are critical
and must be finished on schedule to keep the whole project
on schedule. This project scheduling technique is called
critical path analysis or PERT.)
|
| b. |
For each of the graph models
you have studied - Euler circuits and paths, graph coloring, and critical
paths - describe the types of problems that can be solved using the
model.
Euler circuits and paths help you plan efficient routes.
Graph coloring helps you manage conflicts. Critical paths
help you schedule large projects. |
If you would like to see specific problems from Course 1, Unit 4, a link
is provided to Examples of Tasks from Course
1, Unit 4. If you are interested in following up on the Discrete Mathematics
strand in general, then the Scope and
Sequence will help you see where different concepts are introduced.
On the Discrete Mathematics page, you can
read an explanation of the main discrete mathematics concepts as they
are developed in all four courses.
|
|
