

Course 1, Unit 4  Discrete Mathematical Modeling
Overview
In this unit, students learn basic concepts of an important field of
mathematics called graph theory. In this theory, a graph is a collection
of vertices (dots), some of which are connected by edges. To distinguish
this type of graph from other graphs in mathematics, they are sometimes
called "vertexedge graphs." Students use vertexedge graphs in this
unit to solve problems related to paths, networks, and managing conflicts.
For example, they devise optimal routes for such tasks as delivering
newspapers, collecting money from parking meters, or plowing snow in
a neighborhood street network and they schedule committee meetings to
avoid conflicts when several people are on more than one committee.
Vertexedge graphs are used extensively in business and industry. In
a survey of Fortune 500 companies, vertexedge graphs were identified
as one of the three most commonly used mathematical tools. (The other
two were linear programming and statistical regression.) The mathematics
in this unit is from the Discrete Mathematics
strand of CorePlus Mathematics. A discrete mathematics course
is required for all computer science majors and many mathematics majors.
Also, some discrete mathematics topics are included in college business
management courses.
These graph problems are studied because they are accessible, fundamental,
powerful, and commonly applied in the real world. Furthermore, an important
outcome of this unit is the development of students' skills in mathematical
modeling. Working with graph models provides students with explicit and
invaluable experience in building and using mathematical models. In each
lesson, students first build a graph model that represents a given situation;
then they use the model to find a mathematical solution; and finally,
they interpret the solution in terms of the original situation. In addition,
students explore and reason about properties and algorithms.
Key Ideas from Course 1, Unit 4

Vertexedge graph model: A collection of points called vertices
and line segments or curves called edges. These graphs model situations
such as a route or a set of conflicting conditions. The graph below
has 5 vertices and 8 edges. (See pages 237242.)

Euler circuit: A path around all edges of a graph that starts
and ends at the same vertex, without retracing any edge.

Even degree: A vertex has an "even degree" if there is an
even number of edges coming from that vertex. In the above example, A,
D, and E have even degree. B and C have
odd degree. (See pages 243246.)

Modeling conflict: Vertexedge graphs can be used to model
entities which are in conflict in some way. The conflict is indicated
by an edge joining the vertices; two vertices joined indicate a conflict
and are "colored" in different ways. Vertices that are colored in
the same way are not in conflict; and therefore, are not joined by
an edge. The problem is solved by looking for the number of groups
of same colored vertices necessary. For example, if the above graph
were used to model conflict, A and D would not be in
conflict, because they are not joined by an edge. Thus, A and D could
be "colored" or coded the same. But C is connected to all
other vertices, indicating conflict. So, C must be "colored" or
coded differently. If these vertices represented chemicals, then
it would be safe to store B and E together, A and D together,
but C would have to be kept separate form all others. (See
pages 266275.)

Adjacency matrix: Matrices which are arrays of numbers can
be used to represent the number of edges at each vertex of a vertexedge
graph. A matrix representation for the graph above is as follows:
