I asked if it made a difference which vertex you used as a starting point in problem 5. Students thought it probably did not matter. We explored a few variations and demonstrated that the path chosen needed to be considered carefully in order to minimize traversing the same edge more than once.
With number six, students produced a variety of answers. I was looking to see who produced a minimal path. One group found a path of 36 edges, two more found a 35 edge path, and one found a 33 edge path. I asked a student to present a 33 edge path. As the student drew the solution, the realization came that the path could be completed by traversing 32 edges. And, the path started and ended at the same vertex! The students were somewhat amazed at this result.
The next piece was a bit of historical perspective, showing the origins of graph theory with Euler's bridges of Konigsberg problem. Several students attempted to complete a circuit without crossing any bridge twice. A couple of students thought it would not be possible because of the odd number present.
Presenting a problem like this provides students an opportunity to see how a mathematical idea begins and how it evolves. We go from the concrete map of Konigsberg to a more abstract representation with vertices and edges. The representations are equivalent but the abstract representation displays connections and relations in a clearer manner.
Next, we went through a series of definitions. Mathematical definitions are critical in that they establish a foundation from which everyone agrees and builds upon. Definitions were provided for the following terms:
- Graph
- Vertex
- Edge
- Loop
- Multiple edges
- Adjacent vertices
- Path
- Circuit
- Euler path
- Euler circuit
- Degree of vertex
- Odd vertex
- Even vertex
- Connected graph
- Component
- Cut edge
I was able to use the work that students previously produced to illustrate many of these definitions. For the others, I drew simple graphs that displayed the concept.
At this point I gave students two problems to complete. The first asked students to draw a graph that had 6 vertices, 4 loops, and 2 multiple edges. The second asked students to draw a graph that had 5 vertices, each of degree 4, and contained no loops or multiple edges.
Students worked on the first problem and were discussing and comparing results. As students completed their graphs they were asking if what they had meet the stated requirements. As I told them they did, I could see the sense of triumph in there faces and their reaction to working through the problem. Several students who typically are rather quiet and do not express one way or another how they are doing visibly showed their feeling about successfully completing the task. It was a very cool moment.
Time was running out, so I asked students to tackle the second problem as homework. We will share out solutions to the first problem next class, as there were a variety of solutions. We will also discuss the second problem. Afterward, I will have students work through an additional five problems for next class.
Visit the class summary for a student's perspective and to view the lesson slides.
No comments:
Post a Comment