Geek Answers Handbook

Refining graph terminology

I am working on a homework question and I have an answer, but I'm not sure that the terminology I use is correct, and I was hoping that someone could clarify the situation. Here's the situation:

I have a rectangle graph with size M x N. node at (0, 0) has no incoming edges. All other nodes have incoming edges from the north, northwest, and west, unless they are on the upper or left side, in which case the diagonal inlet edge does not exist, and the edge from the west or north does not exist.

So, if you start with node (0, 0) and follow any path to completion, it ends with node (m, n). Now I was asked to determine what type of chart it is. Is this a directed acyclic graph?

+4
source share
1 answer

Yes, this is because each edge has a direction (hence directed), and there are no loops - as soon as you leave any node, there is no way to return to it following the edges of the graph (therefore, acyclic). See http://en.wikipedia.org/wiki/Directed_acyclic_graph for more details.

+8
source

More articles:


All Articles