My textbook says
Definition 1: A graph, G, is acyclic if it contains no undirected cycles (otherwise
it’s cyclic).
It also says
Definition 2: A (directed) cycle is a (directed) path which begins and ends at the same vertex. An undirected cycle is, likewise, a path beginning
and ending at the same vertex which may or may not respect edge directions.
These definitions confuse me.
By Definition 1, can a graph be acyclic and yet contain a directed cycle? This sounds like a contradiction, but the definition only says an acyclic graph should not contain undirected cycles and says nothing about directed cycles. Unless Definition 1 is implying that all directed cycles can be treated as undirected cycles, but undirected cycles cannot be treated as directed cycles?
Definition 2 seems to reinforce this idea, by suggesting that an undirected cycle can simply ignore edge directions.
On the other hand, I found this website which claims this is a directed acyclic graph:
But by Definition 2, I can just ignore edge direction and create undirected cycles, like $1\rightarrow 2 \rightarrow 5 \rightarrow 6 \rightarrow 3 \rightarrow 1 $, which would make the graph cyclic because it contains undirected cycles. However, the website says it is acyclic, which contradicts everything I've said.
I think I am probably just misinterpreting all of these definitions.
Can we define the terms "acyclic", "cyclic", "undirected cycle" and "directed cycle" in some other way to help clarify what they mean?
Best Answer
Yes, many graph theory textbooks do a better job than yours did. The best way is to start with a firm understanding of (undirected) graphs and move from there to digraphs. So let's start over and eliminate all the useless words.
A cycle is a walk in a graph where the origin and internal vertices are all distinct and the terminus is the same as the origin. A graph is acyclic if it does not contain a cycle.
With that said, a directed graph is one where the edges are all endowed with a direction. Associated with every digraph is its underlying graph which is an undirected graph with the same vertex and edge set but "ignoring" the direction. So when we say that a directed graph is or isn't acyclic, we are implicitly referring to whether the underlying graph is acyclic. But the added structure gives us the notion of a directed cycle, which is a directed walk in the digraph (i.e. one the follows all of the directions) where again the origin and internal vertices are distinct and the terminus and the origin are the same.
The only wrinkle in all of this is that the meddling computer scientists have forced the term directed acyclic graph (DAG) on us. This refers to a digraph that contains no directed cycle (although its underlying graph may contain a cycle). It's not a good name, but there's no putting that toothpaste back in the tube so we have to deal with its existence.
Coming back to the two introductory questions you asked:
No. If a digraph contains a directed cycle, then that same walk in the underlying graph of the digraph would be a cycle. The converse is possible -- a digraph can be cyclic but not contain a directed cycle. The graph you pasted into your question is an example of that.
Yes, as I just noted every directed cycle would be a cycle in the underlying graph. And a cycle in the underlying graph would be a directed cycle in the digraph iff its edges are all following the direction of the walk.
Yes. A cycle is a feature of the underlying graph, so the direction of the edges in the digraph is not considered.
The good news is that all of this is essentially invisible once you have these definitions straight in your mind. Does this clear it up?