[Math] the actual definition of a “Directed Cycle ” in graph theory

computer sciencegraph theorytopological-graph-theorytrees

My question is due to a confusion I have in understanding the definition of a DAG.
From Wolfram Alpha:
"An acyclic digraph [DAG] is a directed graph containing no directed cycles"

However I have not found a proper definition of "directed cycles"!
It must be different from the normal "cycle" definition because:

  1. A two-way edge in a non directed graph is not considered a "cycle"

  2. A regular "directed graph" appears to be able to accommodate two-way edges as seen here. But a DAG do not allow them (I presume? not so clear either…).

Hence, the requirement of no directed cycles eliminates those two way edges.

So, what is the actual definition of a directed cycle?

Best Answer

A directed cycle in a directed graph $(V,E)$ is a sequence of directed edges $(v_1,v_2),...,(v_n,v_1)$ such that whenever $v_{i}$ is vertex in the sequence and $1 \leq i < n$, then there is an edge i$(v_{i},v_{i+1})$. In other words, we must follow the edges in the right order and direction to get back to $v_1$.

Related Question