Course 1, Unit 4 - Graph Models

Summary
In the "Graph Models" 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 find a "critical path" for completing a large project on time, they schedule committee meetings to avoid conflicts when several people are on more than one committee, and they devise optimal routes for such tasks as delivering newspapers, collecting money from parking meters, or plowing snow in a neighborhood street network.

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

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.


  • 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. If all vertices of a graph have even degree, then the graph has an Euler circuit. In the above example, it would not be possible to make a circuit around the graph without retracing any of the edges, because some vertices have odd degree.
  • Euler path: If a graph has only two odd vertices, then the graph has an Euler path; one of the odd vertices must be the start and one must be the end. It is possible to trace a path from start to end without retracing any edge. In the above example, there are 2 odd vertices, therefore an Euler path is possible. One such path is C-D-E-A-E-C-A-B-C-B. (See student book pages 277-280.)
  • 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.
  • Scheduling large projects: The vertices represent tasks, and the edges represent times, a note is added to the edge to indicate these times. The vertices have to be arranged in parallel or sequentially according to the prerequisites in the context.
  • Critical path: The path through the graph which gives enough time for all tasks to be completed.
  • Earliest finish time: The total task time for all tasks on the critical path.
  • 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:
Copyright 2008 Core-Plus Mathematics Project. All rights reserved.