Create a large graph model of the map for a mail carrier to deliver mail to all
Create a large graph model of the map for a mail carrier to deliver mail to all the residences in the neighborhood. This means the intersections will be vertices and the streets will be edges. You will need to put double edges for any streets where there are residences on both sides. However, if there is a park or school on one side then you would use a single edge. See mail carrier graph examples from class videos if this does not seem clear. Your graph model should take up most of an 8 ½ by 11 page and must not be drawn over the map you chose. Some students have used a technique of laying paper over a printout of the map or over their computer screen and drawing the graph with the map as a guide underneath. Please use pencil or black ink for the graph. Or if you want to go completely digital, you may draw your graph using a digital drawing tool. Just be sure the graph is your own work, is in pdf format for viewing, and fills the page.
Answers to three common questions when creating your graph model:
If there is a little piece of street that sticks out and is cut off by my circle around the map, you do not need to include it.
For courts, you can use a double edge or a loop – both are going to work out the same in the end. In my mini sample on the next page, I used double edges.
You can assume there are houses on both sides if the background is grey. Don’t worry about what direction houses are facing. I don’t want it to get too complicated.
3. Highlight any odd vertices on your graph using a highlighter or colored pencil. If you don’t have any odd vertices, write this down under the map.
4. Next add duplicate edges as needed using a different bright color such as red or using dashes to indicate that they are edges that were added after checking for odd vertices to the graph model to EULERIZE the graph. (This will create a graph with all even vertices.) Remember your goal is to add as few duplicate edges as possible so the mail carrier does not have to walk unnecessarily far but you cannot add edges where there were no streets before.
5. Show an Euler Circuit for the mail carrier, indicating where the start and end of the route is, numbering the edges and showing arrows for direction of travel.