Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is every bridge in a graph an edge in DFS search tree?

A question from Skiena's book of algorithm:

Suppose G is a connected undirected graph. An edge e whose removal disconnects the graph is called a bridge. Must every bridge e be an edge in a depth-first search tree of G?

My solution so far (need suggestions):

I think that the bridge is an edge whose end vertex is a cut node, because cut node removal disconnects the graph so removing that edge will also disconnect the graph. Edges in DFS search tree are tree edges & back edges, and only tree edges can be cut edges ( or bridges ) because back edge removal doesn't disconnect the graph.

like image 610
Jake Avatar asked Oct 07 '22 17:10

Jake


1 Answers

Basically, yes. I have some remarks though:

I think that the bridge is an edge whose end vertex is a cut node, because cut node removal disconnects the graph so removing that edge will also disconnect the graph.

This is not exact. Particularly, if you read it as (bridge => edge has a cut node), that is true. But phrased as "a bridge is an edge whose end vertex...", it suggests the converse implication, which is not true. All in all, this sentence is largely irrelevant for the rest of the argument and I'd just omit it.

... only tree edges can be cut edges ( or bridges ) because back edge removal doesn't disconnect the graph.

Yeah, that's it. Plus you have to note that DFS explores all vertices (or labels all edges) of a connected graph.

like image 71
jpalecek Avatar answered Oct 10 '22 06:10

jpalecek