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$

1 Answer 1

1
$\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$
1
  • $\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
    Commented Jan 30, 2018 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .