1
$\begingroup$

If we want to detect and odd cycle if an undirected graph $G=<V,E>$. Suppose we run BFS algorithm from CLRS book as follows,

enter image description here

Q: Now my question is suppose we have the following graphs:

enter image description here

The figure to the left above:

  • $d[v] \bmod{2} == d[u] \bmod{2}$ equal and gives odd cycle.
  • $d[v] \bmod{2} == d[a] \bmod{2}$ not equal remainder, so won't give odd cycle.

The figure to the right above:

  • $d[x] \bmod{2} == d[u] \bmod{2}$ not equal remainder, so won't give odd cycle.
  • $d[x] \bmod{2} == d[v] \bmod{2}$ not equal remainder, so won't give odd cycle.

Problem: so the only case to discover odd cycle is when we have the left right graph and when exactly we compare vertex $v$ distance with $u$ distance. What do you think please? If the mod operator works, can you give your interpretation as why this should work in general please if possible?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The idea, in a nutshell, is that a graph does not contain an odd cycle iff it is 2-colorable (also known as bipartite).

Your algorithm attempts to find a 2-coloring of the graph. In each connected component, the coloring is unique once we fix the color of one of the vertices, since all neighbors of a white vertex are black and vice versa. The algorithm uses this coloring strategy, and verifies that it results in no monochromatic edges.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much. The mod operator above operates on $d[vertex]=distance$, so it assumes that there is an odd if the mod of both vertices are equal, then we have an odd cycle. So I was trying to ask if this will work for general case. So in case of an odd and 2-colorable please, how the odd cycle above would be a 2-colorable and the even cycle to right not please? Can you just give an example please? $\endgroup$ Commented Sep 17, 2021 at 12:29
  • 1
    $\begingroup$ You can try out a sample graph yourself. Just trace the execution of the algorithm. $\endgroup$ Commented Sep 17, 2021 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.