1
$\begingroup$

I suspect that it is not true but I came across with the following statement:

For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross edges.

Is it possible to show an example to disprove it?

$\endgroup$
3
  • 2
    $\begingroup$ What's a cross tree? Also what's an iteration of the DFS algorithm? $\endgroup$
    – Steven
    Jul 22 at 20:16
  • $\begingroup$ @Steven Sorry I meant "cross edge". By "iteration of DFS" I mean, starting from different vertex. $\endgroup$
    – abuka123
    Jul 23 at 10:39
  • $\begingroup$ Is there any particular order in which the edges of the currently visited vertex need to be examined during the DFS? $\endgroup$
    – Steven
    Jul 23 at 10:51
1
$\begingroup$

Consider the following graph:

enter image description here

A possible DFS starting from $a$ visits the vertices in this order: $\langle a, b, c, d \rangle$ producing the cross-edge $(c,b)$.

A possible DFS starting from $b$ visits the vertices in this order: $\langle b, a, c, d \rangle$ producing the cross-edge $(d,c)$.

A possible DFS starting from $c$ visits the vertices in this order: $\langle c, a, b, d \rangle$ producing the cross-edge $(d,b)$.

A possible DFS starting from $d$ visits the vertices in this order: $\langle d, a, b, c \rangle$ producing the cross-edge $(c,b)$.

$\endgroup$
2
  • $\begingroup$ Is it possible to achieve without anti-parallels edges? $\endgroup$
    – abuka123
    Jul 23 at 14:06
  • $\begingroup$ Sure. Just split $(b,a)$, $(c,a)$, and $(d,a)$ by adding a middle vertex. Argue similarly to what I did in the answer to handle depth first searches starting from the newly added vertices. $\endgroup$
    – Steven
    Jul 23 at 14:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.