You are an engineer specializing in urban development. There are multiple towns in a certain region...

 

Transcribed Image Text:

You are an engineer specializing in urban development. There are multiple towns in a certain region that are connected by roads. Some towns have a direct connection between them, but for others you may need to travel through multiple towns. Each road segment is represented by a tuple of the names of the settlements it connects, e.g. (Newton, Needham). The roads are considered bidirectional, the tuple (Newton, Needham) and (Needham, Newton) would represent the same road. (The word "tuple" is a mathematical expression that refers to a pair of elements. We do not refer to the tuple data object in programming.) You are worried about frequent traffic jams. In order to minimize traffic, you decide to build some additional roads in such a way that there are multiple routes between any pair of cities. (It is possible that alternative routes have a different length.) For this you need to identify bottleneck roads. A road (town, town2) is considered a bottleneck if this road is the only way to travel between these two towns. Design an an algorithm that identifies all such bottleneck roads. The algorithm takes as input the tuples representing roads and returns all pairs of cities with a direct connection that is a bottleneck. (Note that you are only asked to indentify bottlenecks, we don't worry about designing the alternative routes.) These kinds of problems often lend themselves to be represented as a graph problem. If you do so, then the first step in your algorithm is to create the corresponding graph. You are an engineer specializing in urban development. There are multiple towns in a certain region that are connected by roads. Some towns have a direct connection between them, but for others you may need to travel through multiple towns. Each road segment is represented by a tuple of the names of the settlements it connects, e.g. (Newton, Needham). The roads are considered bidirectional, the tuple (Newton, Needham) and (Needham, Newton) would represent the same road. (The word "tuple" is a mathematical expression that refers to a pair of elements. We do not refer to the tuple data object in programming.) You are worried about frequent traffic jams. In order to minimize traffic, you decide to build some additional roads in such a way that there are multiple routes between any pair of cities. (It is possible that alternative routes have a different length.) For this you need to identify bottleneck roads. A road (town, town2) is considered a bottleneck if this road is the only way to travel between these two towns. Design an an algorithm that identifies all such bottleneck roads. The algorithm takes as input the tuples representing roads and returns all pairs of cities with a direct connection that is a bottleneck. (Note that you are only asked to indentify bottlenecks, we don't worry about designing the alternative routes.) These kinds of problems often lend themselves to be represented as a graph problem. If you do so, then the first step in your algorithm is to create the corresponding graph.