(20 pts.) Rivers and Roadwork. Your town's urban planner would like to know if any road...

Transcribed Image Text:

(20 pts.) Rivers and Roadwork. Your town's urban planner would like to know if any road in town can be safely closed for repair. A road can be safely closed if doing so does not separate locations that could previously be driven between. Complicating the issue, several rivers cut through your town and can only be crossed by ferry. This means that some pairs of locations could never be driven between, even without roadwork. For example, perhaps a ferry ride is required to get from your house to the town square, but it is possible to drive over some combination of roads from the town square to the grocery store. Any roadwork that separates the town square from the grocery store is unacceptable. However, the fact that you have never been able to drive from your house to the town square is not an issue. Given the layout of every location and road, your goal is to determine whether or not there is any road that can be safely closed. Assume that every road in town is two-way. (a) Model this as a graph problem: give a precise definition of the graph involved. What property of this graph indicates that it has a safe-to-close road? (Hint: If a road can be safely closed, there must be an alternate route connecting its endpoints.) (b) Give an O(IV) algorithm to solve this problem. In your analysis, show that your algorithm's running time is independent of |E|. (Hint: Try to modify the Explore procedure to terminate early when a condition is met.) (20 pts.) Rivers and Roadwork. Your town's urban planner would like to know if any road in town can be safely closed for repair. A road can be safely closed if doing so does not separate locations that could previously be driven between. Complicating the issue, several rivers cut through your town and can only be crossed by ferry. This means that some pairs of locations could never be driven between, even without roadwork. For example, perhaps a ferry ride is required to get from your house to the town square, but it is possible to drive over some combination of roads from the town square to the grocery store. Any roadwork that separates the town square from the grocery store is unacceptable. However, the fact that you have never been able to drive from your house to the town square is not an issue. Given the layout of every location and road, your goal is to determine whether or not there is any road that can be safely closed. Assume that every road in town is two-way. (a) Model this as a graph problem: give a precise definition of the graph involved. What property of this graph indicates that it has a safe-to-close road? (Hint: If a road can be safely closed, there must be an alternate route connecting its endpoints.) (b) Give an O(IV) algorithm to solve this problem. In your analysis, show that your algorithm's running time is independent of |E|. (Hint: Try to modify the Explore procedure to terminate early when a condition is met.)

Answer rating: 100% (QA)

a To model this problem as a graph problem we can create a graph where each location is represented as a vertex and the roads between them are represe... View the full answer