Graph Theory

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.