2
$\begingroup$

I'm seeing seemingly contradictory information about this around. On the one hand, it seems that for undirected graphs, you need at least 3 nodes to make a cycle. On the other other, I've also seen people differentiate between trivial and non-trivial cycles.

Let's say in your directed graph you have two nodes A and B with an edge from A to B and an edge from B to A. Do you have a cycle (A, B)? And does it always count as a cycle, or would some people consider it a cycle and others not?

Also, let's say you traverse that directed graph and hit A before you hit B. Is the edge (B, A) a back edge?

$\endgroup$
2
$\begingroup$

Like most things, you should only care about definition if it makes sense and useful in your context.

And in the context of strongly connected component, a nice property we would like to say is that:

Node $a$ and $b$ belongs to the same cycle if and only if $a$ and $b$ are strongly connected.

Graph with strongly connected components marked

This nice statement only holds if you count $f\rightarrow g\rightarrow f$ as a cycle. So, we would like to count this as a cycle when talking about strongly connected components.

$\endgroup$
  • $\begingroup$ That makes sense, thanks for explaining. $\endgroup$ – jeremy radcliff Feb 12 '17 at 0:21
  • $\begingroup$ Weird. This is simpler than I thought it would be. $\endgroup$ – wogsland Feb 12 '17 at 4: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.