Course 1, Unit 4 - Vertex-Edge Graphs
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 "vertex-edge graphs." Students use vertex-edge 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.
Vertex-edge graphs are used extensively in business and industry. In
a survey of Fortune 500 companies, vertex-edge 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 Core-Plus
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
Vertex-edge 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 237-242.)
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 243-246.)
Modeling conflict: Vertex-edge 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
Adjacency matrix: Matrices which are arrays of numbers can be used to
represent the number of edges at each vertex of a vertex-edge graph.
A matrix representation for the graph above is as follows: