1
$\begingroup$

I was asking to prove that

For any directed graph, when we perform BFS, for each cross edge $(u,v)$, there is some time when both vertices $u$ and $v$ appear in the queue. (In other words, we have a queue like this: $Q = \langle v_1,v_2,..u,..,v,..v_k \rangle$.)

However, when I draw some graph; I've encountered this example

enter image description here

If we perform BFS starts from $a$, then what is the edge of $(f,c)$? clearly, if what I was about to prove is correct, $f$ and $c$ will never appear in the queue at same time during the whole execution of BFS. So $(f,c)$ is not cross edge. Then what edge is this ? It can't be back edge; since $c.parent$ is $a$, and $f.parent$ is $e$. they aren't tree edge, nor forward edge.

So what I am asked to prove is not correct?

So I guess that the statement only holds for undirected graph?

$\endgroup$
  • $\begingroup$ I am afraid your claim is wrong. In this example $(a,b), (a,c), (a,d), (b,e), (e,f)$ are tree edges, no forward and backward edge, and $(f,c)$ is a cross edge. What is the source of this statement? $\endgroup$ – fade2black Aug 9 '17 at 18:12
  • $\begingroup$ @fade2black, it's a question from class; so I guess my instructor made mistake that this statement is for undirected graph, not for directed graph. $\endgroup$ – ElleryL Aug 9 '17 at 18:16
  • $\begingroup$ @fade2black, thanks for the reply; do u mind give me a counter example for undirected graph? I have thinking about this for a while; $\endgroup$ – ElleryL Aug 9 '17 at 18:23
  • $\begingroup$ @ElleryL, I'm pretty sure this is true for an undirected graph. In an undirected graph, BFS should only produce tree edges and cross edges. Cross edges will always be produced if there are cycles in the undirected graph (i.e. $m \geq n$). This is similar to how dfs on undirected graph produces only tree edges and back edges. In particular the cross edge shows up opposite to the "entry-point" of the cycle because it will traverse the cycle in parallel (creating two bfs branches), that then cross over at the end.. $\endgroup$ – ryan Aug 9 '17 at 18:57
2
$\begingroup$

Your statement for directed graphs is not true. Your graph in the OP is a counterexample. However, for undirected graphs it is true since if $(a,b)$ is a cross edge then the depth-difference between the vertices is at most 1, i.e. $depth(a) = depth(b)$ or $depth(a)+1 = depth(b)$. Using this fact, which is proved below, you can prove your statement.

Assume that at some point you have the following queue configuration: $$v_1, v_2,\dots, v_k,a,\dots, u_1,\dots u_m \text{ (leftmost leaves first)}$$ where $v_i$s and $a$ have the depth $d$ and $u_i$s have the depth greater than $d$. Since $(a,b)$ is a cross edge, $a$ and $b$ belong to different ancestral trees, i.e., one of the $v_i$s is an ancestor of $b$ i.e, $b$ must be discovered before we reach $a$. If their depth values are equal then $b$ has already been reached (discovered) and so they must be at the same time in the queue. Otherwise, their depth values differ by 1 and so $b$'s ancestor (parent) must be one of the $v_i$, say $v'$. This $v'$ is popped and extended before we reach $a$ and since $b$ is a descendant of $v'$, $b$ is pushed into the queue before $a$ is removed.

Thus in both cases $a$ and $b$ appear in the queue for some time during the execution of BFS.


Claim: In a breadth-first search of an undirected graph for each cross edge $(a,b)$ $$0 \leq depth(b)-depth(a) \leq 1$$ Proof: Assume that $depth(b)-depth(a) > 1$. Then $depth(b)$ is at least $depth(a) + 2$. But $(a,b) \in E$ (a cross-edge) and hence $depth(b) = depth(a)+1$, a contradiction (see the following figure).

enter image description here

$\endgroup$

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.