2
$\begingroup$

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:

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?

$\endgroup$
8
  • $\begingroup$ Definitions in different sources need not to agree. $\endgroup$ Dec 23 '19 at 15:46
  • $\begingroup$ @MoonLightSyzygy Can a directed graph without directed cycles contain undirected cycles? $\endgroup$
    – Data
    Dec 23 '19 at 15:48
  • $\begingroup$ The graph pictured has undirected cycles, and no directed ones. $\endgroup$ Dec 23 '19 at 15:49
  • $\begingroup$ @MoonLightSyzygy So we could call it a "directed acyclic graph that contains undirected cycles"? $\endgroup$
    – Data
    Dec 23 '19 at 15:51
  • 1
    $\begingroup$ Yes, definitions need not be universal. They are just language. Different people use it differently. If you look at old books you will find that even for defining graph there were tons of definitions. Some people allowing or not, loops, multiple edges, directed edges, ... $\endgroup$ Dec 23 '19 at 15:56
2
$\begingroup$

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?

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:

By Definition 1, can a graph be acyclic and yet contain a directed cycle?

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.

Unless Definition 1 is implying that all directed cycles can be treated as undirected cycles, but undirected cycles cannot be treated as directed cycles?

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.

Definition 2 seems to reinforce this idea, by suggesting that an undirected cycle can simply ignore edge directions.

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?

$\endgroup$
1
  • $\begingroup$ Yes, that does clear it up very well. Great answer. +1 $\endgroup$
    – Data
    Dec 23 '19 at 18:19

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.