1. To deliver mail in a particular neighborhood, the postal carrier needs to walk along each of the streets with houses (the dots). Create a graph with edges showing where the carrier must walk to deliver the mail.
2. Suppose that a town has 7 bridges as pictured below. Create a graph that could be used to determine if there is a path that crosses all bridges once.
3. The table below shows approximate driving times (in minutes, without traffic) between five cities in the Dallas area. Create a weighted graph representing this data.
4. Shown in the table below are the one-way airfares between 5 cities5 . Create a graph showing this data.
5. Find the degree of each vertex in the graph below.
7. Which of these graphs are connected?
9. Travel times by rail for a segment of the Eurail system is shown below with travel times in hours and minutes6 . Find path with shortest travel time from Bern to Berlin by applying Dijkstra’s algorithm.
