1
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.