0
$\begingroup$

I've read over the proof for Robbin's Theorem, but I am not seeing why DFS will always give you a correct orientation of directed edges to solve the problem.

$\endgroup$
  • $\begingroup$ Idea: Think about the augmented DFS procedure for finding bridges. If an edge is a bridge $\leftrightarrow$ there are no back edges in the descendants of the current vertex in the DFS spanning tree. $\endgroup$ – BearAqua Mar 24 '19 at 21:45
  • $\begingroup$ Is there any chance you could expand on that just a bit? I think I get the gist of what you are saying but still not sure. $\endgroup$ – user-2147481704 Mar 24 '19 at 21:58
  • $\begingroup$ Your 2-edge-connected graph is always bridgeless, meaning there's always a back edge to root. What remains is making all the back edges point in the right direction such that there's always a way to visit a vertex's ancestors in the DFS spanning tree. Also - DFS doesn't solve Robbins' theorem; Robbins' theorem states that you can generate a strongly connected digraph from a undirected graph iff the undirected graph is connected and has no bridge. (en.wikipedia.org/wiki/Robbins%27_theorem) $\endgroup$ – BearAqua Mar 24 '19 at 22:10
  • 1
    $\begingroup$ @bearaqua care to write an answer instead of just commenting? $\endgroup$ – John L. Mar 24 '19 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.