Assume you have been recently hired by the Department of Transportation (DoT) to analyze motorized vehicle traffic flows. Your initial goal is to analyze the traffic and traffic delays in a large metropolitan area.

You choose to use a weighted graph to represent this particular scenario. Remember that a graph is a collection of nodes (or vertices) and edges. Each edge will have a corresponding weight.

Describe how you would construct such a weighted graph. What do the nodes represent? What do the edges represent? What values would the weights represent? Is this graph a tree? Justify your design. Feel free to include an example in your description.

Describe an adjacency matrix you might create to represent this graph. What do the rows represent? What do the columns represent? What do the entries in the matrix represent? Feel free to create an example or create an illustration to better explain yourself.

Suppose you wish to identify the shortest travel time between nodes on the graph. What type of path would represent such a route? Describe this path in detail.

Suppose that the DoT is considering repairing some of the roads in the metropolitan area. But first, the DoT wishes to assess each and every road to determine which of the roads require repair. You have reported to the manager of the repair project and noted that you can use your graphical representation and graph-based methods to suggest the most efficient route the inspection crew can take to inspect all the roads. Describe in detail and name the type of the particular path on the graph that would represent this most efficient route. Consider all aspects of travel time undertaken by the inspection crew. Justify your answer.

Suppose that the DoT is planning to widen roads that create a bottleneck in the flow of traffic. As such, you pose this problem as a max flow/min cut problem. You have determined that roads are in need of widening if the traffic flow on the roads is at maximum capacity; these roads are essentially the bottlenecks of the road system. These bottleneck roads can be identified using the Max Flow/Min Cut theorem.

Using the graph representation of the road system, explain how the Max Flow/Min Cut theorem can be used to identify the bottleneck roads.

Create an example graph one might use to analyze this network as a Max Flow problem. Include at least 8 nodes and 16 edges. Include capacities and flows and identify the max flow and/or min cut.