2
$\begingroup$

Below is the definition of a simple cycle in directed and undirected graphs in CLRS:

In a directed graph, a path $\langle v_0, v_1, \dotsc, v_k \rangle$ forms a cycle if $v_0 = v_k$ and the path contains at least one edge. The cycle is simple if, in addition, $v_1, v_2, \dotsc, v_k$ are distinct.

In an undirected graph, a path $\langle v_0, v_1, \dotsc, v_k \rangle$ forms a cycle if $k > 0$, $v_0 = v_k$, and all edges on the path are distinct; the cycle is simple if $v_1, v_2, \dotsc, v_k$ are distinct.

The other sources I've looked at (e.g. wiki) don't make a distinction between unique vertices and edges. I'm guessing there are some cases that require such a distinction to be made, i.e. why do edges not need to be distinct in cycles in directed graphs? Would $\langle v_0, v_1, v_2, v_1, v_2, v_0 \rangle$ be a valid non-simple cycle in a directed graph? (Imagine a triangle with 3 vertices where the path bounces back and forth between two vertices before completing the cycle.)

$\endgroup$
0
$\begingroup$

Imagine a cycle $v_0...v_{k=0}$ which contains a segment that forks at $v_a$ and then reconverges at $v_b$. This will provide two alternate paths (along different edges) from $v_a$ to $v_b$ through the same vertices although both will satisfy $v_0=v_k$.

$\endgroup$
  • $\begingroup$ I apologize - I wasn't thinking straight and asked the wrong question. I edited my question to reflect what I actually wanted to ask. $\endgroup$ – tmakino Jan 30 '18 at 20:22

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.