Difference between Oriented Graph and Directed Acyclic Graphs (DAG)

definitiongraph theory

Definition of Oriented Graph:

Basically directed graphs can have an arrow going from $A$ to $B$ and
an arrow going from $B$ to $A$. Oriented graphs can have at most one
arrow between any two vertices $A$ and $B$.

Definition of Directed Acylic Graph (DAG)

In mathematics, particularly graph theory, and computer science, a
directed acyclic graph (DAG) is a finite directed graph with no
directed cycles
.

An edge from $A$ to $B$ and another from $B$ to $A$ is a cycle right ?

Then if Oriented graphs already do not have such a cycle then how are they different from DAGs ? Unless of course DAGs need some other constraint satisfied ? In that case what are they ?

Best Answer

You are right that $A \rightarrow B \rightarrow A$ would be a directed cycle, but they can be longer. For instance, consider a graph with three vertices $A,B,C$ and edges $A\rightarrow B, B\rightarrow C, C\rightarrow A$. Such a graph is oriented, but it is not a DAG, because there is a cycle.

Related Question