Question

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.

Answer 1

A Graph is a set of vertices connected by edges. If there is a function from set of edges to set of positive real numbers, called the cost function; then the graph is called a weighted graph.

A) To analyze the traffic, we can take nodes to be stations and edges to be roads connecting these stations. The cost function can be taken as the number of vehicle on that road.

For example, if we have to show the situation of 5 vehicles on the road from A to B and 10 vehicles on road B to C, then it can be shown as, .

No, this graph might not be a tree, for example, if we have a road from A to B, B to C and C to A, then the corresponding graph will not be a tree because it will be a cycle. ( a tree is a connected, acyclic graph.)

B) The adjacency matrix is a square matrix used to represent a graph. if we have an edge between i and j then = 1, 0 otherwise. The rows and columns represents the stations and the 0/1 represent whether the corresponding stations are directly connected by a road or not. For example, if we have a road from A to B, B to C and C to A, then it can be represented by the matrix , to show the weights, we have the cost matrix in which 0/1 is replaced by the corresponding weight of the edge ij.

c)The shortest time to travel from Station A to Station Z will be the roads having the least traffic.  Cost of a path is the sum of the cost of all of its edges. To find the shortest time path, we have to find the minimum cost path from A to Z. Minimum Spanning tree(MST) is a subgraph of the given graph such that all the nodes are connected with the minimum possible total edge weight. MST can be helpful to find the shortest path.

d) A Eulerian trail is a cycle containing all the edges. So if we find the minimum weight eulerian trail of a graph, then that road network will be the efficient one to travel via all the roads.