Discrete Math - Day 53

Today we began exploring graphs. I make liberal use of David Clark's Graphs and Optimization course material which can be found on the Journal of Inquiry-Based Learning in Mathematics web site (jiblm.org).

To start things off, I present students with the mail carrier problem. This problem depicts a network of streets. The scenario is that they are offered a job. The supervisor estimates that the work will take a total of 8 hours, including lunch, breaks, and delivery time. The question is whether or not you should take the job.

Students worked through trying different paths trying to minimize the time spent traversing the street network. The network contains 41 segments and the example provided showed a path requiring a total of 53 segments to traverse every block. As students worked they discussed different options and approaches. Two different students came up with paths that took 49 segments. These were shared with the class. The implication was that it would take approximately 9.5 hours to complete the work. Since the supervisor was willing to pay for 8 hours of work, this was not a good job to accept.

Questions arose as to whether there was a single best path and if unique paths existed. These are sound mathematical questions. I was pleased to see students thinking mathematically about the work.

We then moved on to simpler graphs. Students counted the number of segments and then tried to determine a minimal path through the graph. I used the first example, a simple square, to illustrate what they were to do. Students dove into the assignment and started to discuss the need to double back on certain segments.

We discussed the first problem they worked on. The idea of unique paths was resolved as it was easy to demonstrate there were multiple paths that all had the same length. I asked students to complete the work on the next few graphs. We will work on these and look for characteristics that help to identify when there is a need to double back on a segment.

Visit the class summary for a student's perspective and to view the lesson slides.