Bridges

Questions 1 to 5 of 6

1. 1. In the six-vertex graph of this lesson, which edge is a bridge?

   4-50-11-32-0
2. 2. Why does the program skip the parent by edge id (arc.id == parent_edge) instead of skipping the parent vertex?

   Skipping by vertex hides a parallel copy of the edge, so an edge that is not a bridge gets reported as oneSkipping by vertex makes the program slower, because it has to compare more numbersSkipping by vertex stops the walk from ever visiting vertex 0Skipping by vertex gives the root a discovery time of -1
3. 3. What does this program print? ``python def find_bridges(n, edges): adj = [[] for _ in range(n)] for i, (u, v) in enumerate(edges): adj[u].append((v, i)) adj[v].append((u, i)) disc = [-1] * n low = [0] * n timer = 0 bridge_ids = [] is_art = [False] * n def dfs(u, parent_edge): nonlocal timer disc[u] = timer low[u] = timer timer += 1 children = 0 for v, eid in adj[u]: if eid == parent_edge: continue if disc[v] == -1: children += 1 dfs(v, eid) low[u] = min(low[u], low[v]) if low[v] > disc[u]: bridge_ids.append(eid) if parent_edge != -1 and low[v] >= disc[u]: is_art[u] = True else: low[u] = min(low[u], disc[v]) if parent_edge == -1 and children >= 2: is_art[u] = True for u in range(n): if disc[u] == -1: dfs(u, -1) bridges = [edges[i] for i in bridge_ids] articulation = [u for u in range(n) if is_art[u]] return bridges, articulation bridges, articulation = find_bridges(4, [(0, 1), (0, 2), (1, 2), (0, 3)]) print("bridges:", " ".join(f"{u}-{v}" for u, v in bridges)) print("articulation points:", " ".join(str(u) for u in articulation)) ``

   bridges: 0-1 0-2 0-3 and articulation points: 0bridges: 0-3 and articulation points: 0bridges: (none) and articulation points: 0bridges: 0-3 and articulation points: 0 1
4. 4. Which vertices does the articulation points line print for this program? ``python def find_bridges(n, edges): adj = [[] for _ in range(n)] for i, (u, v) in enumerate(edges): adj[u].append((v, i)) adj[v].append((u, i)) disc = [-1] * n low = [0] * n timer = 0 bridge_ids = [] is_art = [False] * n def dfs(u, parent_edge): nonlocal timer disc[u] = timer low[u] = timer timer += 1 children = 0 for v, eid in adj[u]: if eid == parent_edge: continue if disc[v] == -1: children += 1 dfs(v, eid) low[u] = min(low[u], low[v]) if low[v] > disc[u]: bridge_ids.append(eid) if parent_edge != -1 and low[v] >= disc[u]: is_art[u] = True else: low[u] = min(low[u], disc[v]) if parent_edge == -1 and children >= 2: is_art[u] = True for u in range(n): if disc[u] == -1: dfs(u, -1) bridges = [edges[i] for i in bridge_ids] articulation = [u for u in range(n) if is_art[u]] return bridges, articulation bridges, articulation = find_bridges(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)]) print("bridges:", " ".join(f"{u}-{v}" for u, v in bridges)) print("articulation points:", " ".join(str(u) for u in articulation)) ``

   2 310 1 31 3
5. 5. In the bridge rule, the tree edge from u to its child v is a bridge when low[v] is greater than what value?

   Type your answer.