Graphs, Paths, & Circuits Lesson

Adapted from Course materials (VII.A Student Activity Sheet 1,3, & 4) for AMDM developed under the leadership of the Charles A. Dana Center, in collaboration with the Texas Association of Supervisors of Mathematics and with funding from Greater Texas Foundation.

In this lesson, you will explore a type of mathematical model that provides a representation of reality and communicate mathematically by completing the Euler Circuits and Path task in your notebook. Be prepared to discuss your solutions with your peers.

As with other mathematical models, graphs are used to translate mathematical procedures (arithmetic and pattern recognition mostly) in order to shed light on real-world or physical problems. The use of a graph in this unit is not to be confused with the use of a graph in the context of graphing functions. This meaning of the word graph is entirely different from its meaning in "the graph of a function." There are many ways to represent the same graph. For example, the following are all considered the same graph because they each consist of two vertices connected by a single edge:

For each of the vertices of a graph, the order of the vertex is the number of edges at that vertex. The degree of a vertex is the number of edges connected to that vertex. For example, each of the vertexes in the graph below have a degree of two.

Some graphs contain loops, edges that begin and end at the same vertex. The following is a graph with a loop:

Sometimes multiple edges between the same two vertices are allowed. When making conjectures, it must be clear if such things as multiple edges and loops are being considered.

The Snowplow Problem

Sometimes more information needs to be conveyed in a graph. For instance, in the Königsberg Bridge problem, the focus was on the parts of land connected by bridges. Some problems require consideration of how long (in terms of distance or time) it takes to traverse a given edge. The graphs that appear in this lesson have weights associated with their edges. As with many mathematical problems, the focus is on finding extreme paths (that is, paths that maximize or minimize a certain quantity).

As the new snowplow operator, you must decide the best route through three cities. The best route saves money. In each city, you need to plow all the roads and return to your starting place, but you must also keep from backtracking as much as possible.

Construct two snowplow routes through each of the following cities, starting at point A and ending at point A, and indicate the time it will take to travel each route. Notice that the length of the lines do not indicate the amount of time. The time it takes to traverse each road (in hours) is indicated in the graph.

How would you solve the Snowplow problem for a graph that has no vertices of an odd degree (vertices with degrees of 1, 3, 5, 7, etc)?

If the graph contains vertices of only an even degree, it must contain a Euler circuit meaning there is a path through the graph that uses each edge exactly once. Therefore, no backtracking is required.

City I has two vertices of an odd degree.

Find these vertices and the shortest path between them. Answer: Vertices C and D have an odd degree (both have a degree of 3), and the shortest path between them is CEBD ( or the reverse path, DBEC). This path is 8 hours.
For each edge in this shortest path, put in a second copy of the edge.

City I has two vertices of an odd degree.

At this point, your graph should have no vertices of an odd degree. Find a Euler circuit and compare this path with the paths you found for City I.

One example of an Euler circuit in this graph is ABDFEDBCEBECA, which takes 45 hours. There are other Euler circuits, but they all yield the minimum time of 45 hours.

Self-Assessment: City III

Follow the procedure outlined in above to find a solution to the Snowplow problem for City III.

Follow the procedure outlined in above to find a solution to the Snowplow problem for City III.

Map with second routes
text annotation indicator

Map with second routes

Answer

Vertices A and E are the only two with an odd degree, and the shortest path from A to E is ACE. Therefore, you double those edges, yielding the graph below.

A path on a graph that goes through each vertex once is called a Hamiltonian path. A path that starts and stops at the same vertex and goes through each vertex once is called a Hamiltonian circuit. Which of the following graphs have a Hamiltonian circuit?

A path on a graph that goes through each vertex once is called a Hamiltonian path

Graph I has a Hamiltonian circuit.
Graph II has a Hamiltonian circuit. This type of circuit only needs to pass through all vertices; it can have unused edges. So, the same path in Graph I can be used in Graph II. Adding edges from Graph I to Graph II does not affect the Hamiltonian circuit.
Graph III does not have a Hamiltonian circuit.
Graph IV has a Hamiltonian circuit.

There is no single distinguishing feature that can guarantee the existence of a Hamiltonian circuit. There are, however, some special types of graphs that have Hamiltonian circuits. Some possibilities that the previous examples might point to include the following:

Consider any graph like Graph I that forms the edges of a polygon. The polygon could have any number of sides (edges).
Begin with any polygon (like Graph I) and add extra edges anywhere (like Graph II). The resulting graph has a Hamiltonian circuit.
Take a graph like Graph IV that has an outer polygon and an inner polygon with the same number of edges. If each vertex of the outer polygon is connected to a similar vertex of the inner polygon, the resulting graph has a Hamiltonian circuit.

Compare and contrast an Euler circuit and a Hamiltonian circuit.

These circuits are similar because each is defined by no repetitions or exclusions, or stated differently all parts are included exactly once.
An Euler path is a path that crosses every edge exactly once without repeating, if it ends at the initial vertex then it is an Euler circuit.
A Hamiltonian path passes through each vertex (note not each edge), exactly once, if it ends at the initial vertex then it is a Hamiltonian circuit.
They are different in that an Euler circuit is focused on the edges of the graph, while a Hamiltonian circuit is defined by the vertices of the graph.
In an Euler path, passing through a vertex more than once is allowed.
In a Hamiltonian path, you may not pass through all edges.

IMAGES CREATED BY GAVS