2
$\begingroup$

I have been through multiple definitions of DAG and all of them say that it is a directed graph without cycles. Also, it is said that it has topological ordering.

Now the following figure is directed graph and does not have cycles.

enter image description here

But looking at the ordering of edges (look at edge (2,1)), it is not topologically ordered.

Is this still a DAG or every edge must be topologically ordered for this graph to be a DAG??

$\endgroup$
5
$\begingroup$

The acronym DAG stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering.

In your example you have a labeled DAG. The labels do not constitute a topological ordering of the DAG, but the underlying digraph is still a DAG.

$\endgroup$
3
  • $\begingroup$ cannot upvote because of less reputation, but it was the answer i was searching for. $\endgroup$ – Navjot Singh Mar 23 '18 at 17:38
  • $\begingroup$ You should be able to accept the answer. $\endgroup$ – Yuval Filmus Mar 23 '18 at 18:16
  • $\begingroup$ I prefer the term "acyclic directed graph" (ADG) for what is commonly called a directed acyclic graph (DAG) because it seems a more accurate description. I suspect that DAG is more popular only because it is easier to pronounce in English. $\endgroup$ – Simon Apr 6 '18 at 14:24

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.