Question

Problem 5: Aging Infrastructure [20 points Around the United States, subway systems that were built decades ago are ages. New York, Washington DC, and several other metropolitan areas have experienced recent disruptions in their subway service as a result of outages caused by aging infrastructure. At its core, any subway system is defined by its set of stations and the track segments that connect pairs of stations. Consider the need to intentionally take a segment ofa subway system out of commission to update it (e.g., to replace tracks, upgrade signals, etc.). We assume that the stations are fine, but segiments connecting stations may need updating. The city would like to ensure that, during transit hours, it is always possible to get from any given subway station to any other subway station, even i a particular segment of the subway system is closed for construction. However, some subway segments are critical, that is, they represent the only way to get from one station to another. The city would like to determine where these segments are and schedule their maintenance for times outside of the subway system's operating hours (e.g., between 11:30pm and 5:00am on Washington DC) starting to show their weekdays in (a) [5 points] Describe the graph-based data structure you would set up to represent the data given. Make sure to outline: what are the vertices? what are the edges? directed or undi- rected? weighted unweighted? or

Answer 1

1. In given graph Cities are vertices and subway are edges.Graph is undirected as we can go A to B and can also come back. Unweighted graph.

2. Even after removing a edge if a graph is connected then the edge is not critical otherwise it is critical edge.

Tarjan algorithm for finding bridge . This algorithm mainly maintains two array dis[ ] and low[ ]. dis array mainly contain number of dfs call we needed to get to this node and low contains smallest number of call to reach a vertex which is connected to our vertices . If u,v is connected and u is parent of vand low[v]>dis[u] then u,v is a bridge.

int dfs(int i)

{

static int time=0;

int cou_o_children=0; // count of children

vis[i]=true; dis[u]=low[u]=++time; // make current node as visited and intialise time to get to that node and minimum time to get to that node

for(auto k=v1[i].begin();k!=v1[i].end();k++)

{

if(vis[*k]==0)

{

par[*k]=i; dfs(*k);

low[i] = min(low[i], low[*k]); // check subtree rooted at *k has connection with one of ancestor of i

if (low[*k] > disc[i]) // it means *k and i is critical subway.

}

else if (*k != parent[i]) // update low value for i

low[i] = min(low[i], disc[*k]);

}

}

3. Critical edge are also called bridge edge . Time complexity of most efficient algorithm is O(V+E) using adjacency lists. Basically in this algorithm we are doing dfs . In DFS tree an edge (u, v) is bridge if there is no way to reach u or an ancestor of u from subtree rooted with v if we remove edge between (u,v).