Course 1, Unit 4 - Vertex-Edge Graphs

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 "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 pages 266-275.)

• 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: