Graph Theory

6 Comments

An administrator told me about a problem from the world outside school he faced while building his home last year. He had gone to the post office to confirm the location in which he wished to place his mailbox was acceptable to the U. S. Postal Service mailbox guidelines. The administrator poured the footing and ordered the stone for the mailbox. A few days later, the mail delivery person informed the administrator the mailbox placement was incorrect. As a result of a miscommunication, the Post Office instructed the administrator to move his mailbox, causing the administrator to lose his considerable fiscal investment in the mailbox. The issue has to do with the route the mail delivery person drives each day. Below is a map of the neighborhood in question.

Mailbox_Problem_Map_Mr_S_Adj

Exhibit A: The neighborhood. Mailboxes appear as an "X." The house in question is drawn in red. Street names have been suppressed to protect the innocent. Red ovals indicate either a cul-de-sac or a potential entrance from a main road into the neighborhood.

Some background information: mail delivery personnel prefer not to get out of their vehicle. Many mail delivery vehicles have the driver's side door on the right hand side, so a person could infer the mail delivery route using the condition the mailbox must be on the right hand side of the delivery vehicle.

The administrator came to our classroom Thursday. He served as a guest speaker for twenty minutes, drawing the annotations on the Google Maps image. It reminded me of a press conference format; the students asked questions about relevant and irrelevant information in an effort to fully understand the problem.

This problem is the perfect follow-up to the "Chomp the Graph" activity on graph theory. Students can investigate routes using directed paths. Students can compute distances by coordinatizing the image and applying the scale which appears in the lower left. What the students really want to know is whether it is possible to optimize the mail route in a way that benefits the administrator. My students will work on this problem next week in the computer lab. I am eager to see where the investigation takes us.