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
graph
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