Question

In: Advanced Math

Assume you have been recently hired by the Department of Transportation (DoT) to analyze motorized vehicle...

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.

Solutions

Expert Solution

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.


Related Solutions

You have been recently hired in the human resources department at the company you have always...
You have been recently hired in the human resources department at the company you have always dreamed of working for. At the end of your first day, your manager, I. M. DeBoss, on her way out of the office says to you: “So Mr./Ms. Jones, what things come to mind when you think of the word “ethics”? Before you can answer, she asks you if you believe ethics are important for a company and if so why do you feel...
You have been recently hired in the human resources department at the company you have always...
You have been recently hired in the human resources department at the company you have always dreamed of working for. At the end of your first day, your manager, I.M. DeBoss, on her way out of the office says to you: “So Mr./Ms. Jones, what things come to mind when you think of the word 'ethics'?" Before you can answer, she asks you if you believe ethics are important for a company and if so why do you feel that...
Assume that you have recently been hired as the special assistant to the chief executive officer...
Assume that you have recently been hired as the special assistant to the chief executive officer (CEO) of your health care organization, Thunder Hospital. Your duty is to head up the new quality improvement department. Over the last year, the hospital has experienced substantial growth but is also facing a number of patient safety concerns, including a steady increase in medical errors and a 25% rise in hospital-acquired infections. Based upon what you have learned in this course, prepare a...
You have recently been hired by Middleton Manufacturing to work in the newly established treasury department....
You have recently been hired by Middleton Manufacturing to work in the newly established treasury department. Middleton Manufacturing is a small company with disorganized systems and the finance area needs work. The company currently has a beginning cash balance of $100,000 and plans to buy new machinery during the fourth quarter for $500,000, paying cash. The company maintains a minimum cash balance of $100,000 and invests any excess cash in a money market account. The company borrows short-term from CIBC,...
You have recently been hired by Piepkorn Manufacturing to work in a newly established treasury department....
You have recently been hired by Piepkorn Manufacturing to work in a newly established treasury department. Piepkorn Manufacturing is a small company that produces cardboard boxes in a variety of sizes for different purchasers. Gary Piepkon, the owner of the company, works primarily in the sales and production areas of the company. Currently, the company puts all receivables in one shoe box and all payables in another. Because of the disorganized system, all finance area needs work, and that’s what...
You have recently been hired by a state health department to direct surveillance activities for notifiable...
You have recently been hired by a state health department to direct surveillance activities for notifiable diseases, among other tasks. All notifiable disease surveillance data are entered and stored in computer files at the state and transmitted to CDC once each week. CDC publishes these data for all states in the MMWR each week, but health department staff do not routinely review these data in the MMWR. The state has never generated its own set of tables for analysis and...
Assume you have recently been hired as a new manager of EyeTech Company, an innovative company...
Assume you have recently been hired as a new manager of EyeTech Company, an innovative company that sells specialized eye care treatment equipment to Ophthalmologists, Optometrists, clinics, and hospitals. Over the course of your first year, you will face 4 challenges as set forth below: 1. March 2. June 3. September 4. December. Respond to each and every challenge one at a time with insights you have gained from your study of the material presented in modules 1 through 5....
Assume that you have just been hired by Tampa Electronics in their internal Audit department. Ms....
Assume that you have just been hired by Tampa Electronics in their internal Audit department. Ms. Gonzales has asked you to undertake the task of examining the travel expese data to determine whether there are any potentially fraudulent travel reimbursements. In addition to clear violations of the company's rule e.g., an approval being used for multiple trips, an expense reimbursement without an approval, you should be looking for indicators of potentially fraudulent travel expense reimbursement
You have recently been hired by Bio Lux Company, in its relatively new treasury management department....
You have recently been hired by Bio Lux Company, in its relatively new treasury management department. Bio Lux was founded five years ago by Jessica Parker. Jessica found a method to produce high quality shampoo using natural ingredients. The shampoo produced by Bio Lux is in a good position to compete with other more established shampoo producers. The company is privately owned by Jessica Parker and her family, and it had sales of $12 million last year. Bio Lux primarily...
You have recently been hired by Bio Lux Company, in its relatively new treasury management department....
You have recently been hired by Bio Lux Company, in its relatively new treasury management department. Bio Lux was founded five years ago by Jessica Parker. Jessica found a method to produce high quality shampoo using natural ingredients. The shampoo produced by Bio Lux is in a good position to compete with other more established shampoo producers. The company is privately owned by Jessica Parker and her family, and it had sales of $12 million last year. Bio Lux primarily...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT