CODEWITHSUNDEEP
algorithmgraphdepth-first-search
Wayne Rooney
Wayne Rooney

Reputation: 1607

Articulation points and bridges in a graph

Today I learned about articulation points and bridges in a graph(basically undirected).

The text from where I read ( a book by steven-halim) says

When we are in vertex u and v is its neighbor, then if dfs_low(v) >= dfs_num(u) then u is a cut vertex.

Whereas ,

The condition becomes dfs_low(v) > dfs_num(u) while checking for bridges.

But I cannot figure out why the equality is gone from the second case(in bridges). Please help me with this.

PS: dfs_num(i) numbers the vertex as seen in dfs.

dfs_low(i) tells the lowest numbered vertex reachable from i other than its parent.

Upvotes: 2

Views: 1564

Answers (1)

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8711

Suppose in the situation being considered that u is an articulation point but u-v is not a bridge. Then there will exist a path from v to u other than via the u-v link; hence a DFS that passes from the biconnected component containing u to that containing v will eventually reach u again, providing for equality in dfs_low(v) >= dfs_num(u). (The greater-than part of the inequality occurs because u is an articulation point, so a path from v cannot get to lower-numbered vertices without passing through u, and DFS does not retrace such paths.)

But if u-v is also a bridge, there will not exist any other path between v and u than via the bridge u-v. So the DFS will never reach u again; and all of the dfs_num values after the DFS reaches v will be strictly larger than dfs_num(u).

Upvotes: 3

Related Questions