Graph Optimization in Transportation Networks
Consider an urban area modeled as a weighted graph where intersections are nodes and streets are edges. Each edge is assigned two distinct weights: one for the construction cost and another for travel time. Your task is to formulate a comprehensive network model and analyze it from different optimization perspectives. Refer to parts (a) and […]
Part a
Design a connected weighted graph to model an urban transportation network. Describe how you would apply a Minimum Spanning Tree (MST) algorithm (such as Kruskal’s or Prim’s) to ensure that all intersections are connected with the minimum total construction cost. Include details on how nodes and weighted edges are defined in your model.
Optimizing Network Connections with MST and Shortest Path
A telecommunications company is designing a network to connect six cities (A, B, C, D, E, F) with communication cables. The distances between cities (in km) are given as weighted edges in the following network graph:\n\n- City A to City B: 4 km\n- City A to City C: 3 km\n- City B to City C: […]
Part a
Construct the Minimum Spanning Tree (MST) for the telecommunications network. List the edges included in your MST and calculate the total weight of the MST.
Part b
Determine the shortest path from city A to city F in the original network graph. Then, identify if any minimal extension is needed to the MST so that this shortest path is included within the MST. If an extension is needed, specify the edge(s) to be added.
Uniqueness of Minimum Spanning Trees
Explain, using the cut property, why a minimum spanning tree (MST) is unique if all edge weights in the graph are distinct.