When can I be sure a directed graph is acyclic?

Posted by Daniel Scocco on Programmers See other posts from Programmers or by Daniel Scocco
Published on 2011-11-12T12:46:44Z Indexed on 2011/11/12 18:06 UTC
Read the original article Hit count: 316

Filed under:

The definition for directed acyclic graph is this: "there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again."

So far so good, but I am trying to find some premises that will be simpler to test and that will also guarantee the graph is acyclic. I came up with those premises, but they are pretty basic so I am sure other people figured it out in the past (or they are incorrect). The problem is I couldn't find anything related on books/online, hence why I decided to post this question.

Premise 1: If all vertices of the graph have an incoming edge, then the graph can't be acyclic. Is this correct?

Premise 2: Assume the graph in question does have one vertex with no incoming edges. In this case, in order to have a cycle, at least one of the other vertices would need to have two or more incoming edges. Is this correct?

© Programmers or respective owner

Related posts about graph