For whatever reason, there were quite a few students missing at the start of class today. It's AP testing time, so I wasn't sure if half the class was missing due to AP tests or if the students just didn't want to get out of bed on a rainy morning during the last week of school.
I was intending to go through some additional theorems regarding Euler paths and circuits but there were so many students out I knew I had to change direction. I decided to tie graphs back to physical reality. Relating back to how we started with the Konigsberg bridge problem, I asked the class what a graph of our school would look like? We briefly discussed what should represent edges and vertices and I let them work on the problem for a while.
As students worked on the graph I walked around to see what they were doing. Several students wanted to make a physical representation of the school layout with vertices representing the intersections of walls and the like. I referenced back to the Konigsberg bridge problem and the fact the land masses and island represented the vertices and the bridges that connected these land masses represented the edges. With these brief discussions I was able to get these students on a better path to representing the school layout.
As we did this work, more students trickled into class until I had almost a full compliment of students. These students' groups helped to get the new additions up to speed. I allowed students to go through the building to be sure they were getting a good representation of the layout. A few groups availed themselves of this opportunity.
We took a look at the graphs that were created. Most of the groups had essentially the same graph (see below).
The graphs correctly identified the five major landing areas and the fact that two of the school's wings contained four stairways each and were connected by a catwalk on the upper floor and a walkway on the lower floor. The question I posed to the class was whether or not an Euler path existed in this graph?
Students made several attempts but failed to find a path. They asked if they could go out and try walking paths. I let those that wanted go make the attempt. About five or six students remained in class. These students were typically the ones that were not as engaged. I told this group that an Euler path did exist and they needed to find one. They all were busy working on the problem when within two or three minutes one student called out, "I go it!" Everyone else looked up in amazement as this student rarely looked like he even paid attention in class. I had him go to the board and he quickly drew his Euler path. Everyone else was in awe and said how amazing it was. He even joked about being the kid who never pays attention but was able to solve the problem. It was an exciting win for him and I appreciated the positive, supportive reaction from those present.
A few minutes later one of the groups who left came rushing in saying they found the solution and, not seeing any other groups back, that they must be the first. The students who stayed pointed out that the problem had already been solved. As this discussion took place a couple of other groups returned, one who was successful in determining an Euler path and one that was not.
We shared out the solutions and discussed why the attempts to start at one of the even vertices did not work out whereas starting out at one of the odd vertices did work out. Again, one of the students who tends to struggle in class voiced the opinion that when you start at an odd vertex and leave, you in essence make the vertex even. This even vertex can now be paired up to go back to the vertex and leave again. While not a formal proof, it clearly showed the student was thinking about the problem from a mathematical perspective and using the properties of the graph to reason about the outcome.
We discussed this further. With an odd vertex, at some point you either have to leave or return to it. If it isn't the starting or ending vertex this means that you would have to double-back on an edge, resulting in a path that is not an Euler path.
About this time, a group who decided to make a more detailed graph of the school returned. They attempted to include classrooms, alcoves, and other areas located throughout the school. It was an impressive attempt that made a much more detailed representation of the school, breaking wing floors into subsections. The image below shows their graph.
This graph shows the three wings of the school but provides more detail for each level and for classrooms. Students asked questions to clarify what they were viewing but we all felt they had created a good graphical representation of the school.
I next showed a short video about creating a graph of a house. This reinforced some of the ideas that students had been wrestling with regarding paths and circuits.
With that, I went through some of the material I was intending to cover today. Specifically, we looked at the Odd and Even Vertex Theorems.
Odd Vertex Theorem
Suppose A is an odd vertex of a graph.
1. An Euler path that starts at A cannot end at A.
2. An Euler path that does not start at A must end at A.
3. Every Euler path either starts or ends at A.
Even Vertex Theorem
Suppose B is an even vertex of a graph.
Every Euler path that starts at B must also end at B . This ?means the path is an Euler circuit.
We discussed these theorems in light of what students had been investigating and see with their graphs today. Students seemed to understand why an Euler path must start and end on odd vertices. The video along with our work also helped to make sense of the Even Vertex Theorem. The basic reasoning here was that as I leave an even degree vertex, there are now an odd number of edges left that go to that vertex. Getting rid of even pairs by traveling in and out, I can reduce this number to a single edge that has not been traveled. If the edge is traversed before the path is complete, then the only way to leave the vertex is to double-back, resulting in a path that is not an Euler path.
I asked what this meant for other graphs. I drew an example, where the graph had three vertices of degree 3, one vertex of degree 1 and one vertex of degree 2. See the image below.
I asked students what they could tell me about whether or not this graph had any Euler paths or circuits. Students realized an Euler circuit could not exist because the circuit would have to start at the sole even vertex. But this would mean that the vertex of degree 1 could not be included.
The question of an Euler path was more difficult for them determine. Several students made unsuccessful attempts. Their discussions quickly turned to considering that maybe it was not possible to draw an Euler path. I asked students which of the odd vertices would they start at and which would be used as the starting point. How could you decide?
Again, students quickly realized the degree 1 vertex would either have to be the starting vertex or the ending vertex. I pushed them to consider if they started at the degree 1 vertex, how could they determine which of the remaining odd vertices to use as the ending vertex? I then asked them to consider what happens with the remaining two odd vertices?.
Pick one of the two remaining odd vertices. You traverse one edge to reach the vertex. To leave you must traverse another edge. This means to go to that vertex and leave it again you must use two edges. However, there are an odd number of edges, so at some point there will only be on edge remaining. This edge must be traveled, but it is not the last edge in the graph, since we are not ending our path at that vertex. Therefore there is not an Euler path in this graph.
After this discussion, I displayed the first Euler Path and Circuit Theorems.
First Euler Path Theorem
If a graph has an Euler path, then
- it must be connected and
- it must have either 0 or 2 odd vertices.
First Euler Circuit Theorem
If a graph has an Euler circuit, then
- it must be connected and
- it must have no odd vertices.
The previous discussions and investigations proved these theorems in a somewhat informal manner, but the reasoning was sound enough to provide a convincing argument.
We'll explore a few more theorems about circuits and paths to wrap up the semester.
Visit the class summary for a student's perspective and to view the lesson slides.
No comments:
Post a Comment