29
$\begingroup$

How can you correctly reason that this directed graph is acyclic?

enter image description here

I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is equal to the ending vertex. But is this actually a reason you can say if someone asks you?

Is there maybe some kind of rule / formula where you can determine this by comparing the amount of vertices with the amount of edges?

We have here $6$ vertices and $10$ edges.

I hope you can give me some help because if someone asks me why this directed graph or generally a directed graph is acyclic, I would go like that here and I don't feel good about it.

$\endgroup$
  • 3
    $\begingroup$ Aside from the fact that you could delete both $A$ and $F$ together at the first stage as vertices with "all in" or "all out" arrows, and repeat the test at each stage, which might be more efficient on a larger directed graph, the answers you have deal well with your example. If your reduction leads you to a situation where every vertex has both in and out arrows, just take a path and keep going. If you get to a point where you have no option, you must have visited it before (every point has an out arrow, so you've already used it), and hence it is easy to see that there is a cycle. $\endgroup$ – Mark Bennet May 24 '18 at 21:58
  • $\begingroup$ You may get an answer from the powers of adjacency matrix... $\endgroup$ – DVD May 31 '18 at 2:35
48
$\begingroup$

Step 1. Since $A$ has no indegree it can't be part of any cycle. So remove it. We have now graph $G_1$.

Step 2. Since $C$ has no indegree it can't be part of any cycle (in this new graph $G_1$). So remove it. We get $G_2$

Step 3. Now in $G_2$ nodes $B$ and $D$ have no indegree so remove them.

$\endgroup$
  • 4
    $\begingroup$ you can remove B also in step 2. $\endgroup$ – HRSE May 25 '18 at 8:35
  • 1
    $\begingroup$ @HRSE Yes we can... $\endgroup$ – Aqua May 25 '18 at 9:08
  • 18
    $\begingroup$ That is the algorithm to find a topological ordering of the graph. If when you stop you still have nodes remaining, then the original graph is not acyclic. If no nodes remain, then the original graph is acyclic, and you've found a topological ordering $\endgroup$ – Ant May 25 '18 at 9:58
57
$\begingroup$

A more general approach to this is given by topological sorting. In particular, a topological sort exists if and only if the graph is a directed acyclic graph. The 'algorithms' described in the other answers effectively perform a topological sort, in that they repeatedly remove vertices with no incoming/outgoing edges.

For instance, a topological ordering of your graph is given by $A,B,C,D,E,F$ and if you redraw the graph so that the earlier vertices are higher than later vertices (not necessarily linearly) you can see that there are no 'upward' edges, so there can be no cycle.

$\endgroup$
  • $\begingroup$ I like this answer because it provides an answer which works on other graphs besides this one. I also believe the first algorithm on the Wikipedia page (Kahn's algorithm) is indeed the algorithm ChristianF has spelled out in his answer. $\endgroup$ – Cort Ammon May 24 '18 at 22:02
  • $\begingroup$ @CortAmmon Yes, and if you reverse all edges then the algorithm described by Arnaud is Kahn's algorithm also. $\endgroup$ – B. Mehta May 24 '18 at 22:04
  • $\begingroup$ In the specific example, rotate the given image by a tiny angle clockwise. Then every arrow has a downward component. $\endgroup$ – Hagen von Eitzen May 26 '18 at 16:49
  • $\begingroup$ @HagenvonEitzen I like this argument too! Certainly cleaner than redrawing the whole graph. $\endgroup$ – B. Mehta May 26 '18 at 20:16
12
$\begingroup$

A directed cycle can't involve $F$ since no arrows start from $F$. So you can delete $F$ and all arrows that land at $F$ from the graph. The original graph is acyclic if and only if the new graph is.

Repeat the procedure with $E$ now. Then with $D$, then with $B$ and $C$.

In the end, only $A$ remains, with no edges, that is an acyclic graph.

$\endgroup$
7
$\begingroup$

As B. Mehta's answer indicates, you can solve this problem in the general case by topo-sorting. Here's a quick guide to how to do that:

  • Start by coloring every node green.

Now do the following steps for every node:

  • If the node is red, skip it. We've already checked it for cycles.
  • If the node is yellow, you've got a cycle. We're done.
  • The node must be green. Recolor it yellow.
  • Re-start this algorithm for all the outgoing neighbours of the current node.
  • When they're all done, color this node red.

Once you're done that, either you encountered a yellow node, or you did not. If you did not, there is no cycle. If you did, then there is a cycle, and it contains the yellow node.

Let's look at your example. We start with everything green. Let's suppose that we're going to look at the nodes in order A, B, C, D, E, F.

A becomes yellow. We must now look at B, C, D next.
  B becomes yellow. We must look at E next.
    E becomes yellow. We must look at F next.
      F becomes yellow.
      F becomes red. 
    E becomes red.
  B becomes red.
  C becomes yellow. We must look at F next.
    F is red, so we skip it.
  C becomes red.
  D becomes yellow. We must look at E and F next.
    But they are both red, so skip them.
  D becomes red.
  A becomes red.
B, C, D, E and F are all red, so we're done, and the graph is acyclic.

Now suppose we have A -> B -> C -> A. They're all green.

A becomes yellow; we have to look at B next.
  B becomes yellow; we have to look at C next.
    C becomes yellow; we have to look at A next.
      A is yellow. There is a cycle.

Make sense?

Bonus algorithm: Suppose the graph is acylic. When you color a node red, put an increasing number on it. In our example, F = 1, E = 2, B = 3, C = 4, D = 5 A = 6. If you removed the nodes from the graph in that order, you would never remove a node that had an outbound edge.

That's why this is called "topological sort". It lets us find an order on a DAG where an arrow pointing from A to B means "task A cannot be done until after task B is done". In our example, F has to be done first, and sure enough, it is. We remove F from the graph, and now E has to be done next. We remove E from the graph and now B, C or D are equally good so we can do them, and then we must do A last.

$\endgroup$
4
$\begingroup$

I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is equal to the ending vertex. But is this actually a reason you can say if someone asks you?

Not if you can't prove it, but in your particular example, you can very easily do so, and that makes it a valid approach to use here.

Move F down a little bit. Once you've done that, all edges and therefore all (non-empty) paths go from top to bottom, so trivially, there can be no path from a vertex to itself.

$\endgroup$
  • $\begingroup$ I like how this geometrically represents a potential function on the vertices using the $y$ coordinate. A finite directed graph is acyclic if and only if there is a function $\Phi:V\to\mathbb{Z}$ such that $\Phi(v)-\Phi(w)>0$ whenever there is an edge from $w$ to $v$. (I guess in the language of simplicial homology, iff there is a $0$-cochain whose coboundary is in the positive cone.) For a planar directed graph, a topological sort can also be represented as a collection of "isopotential curves" that edges are only allowed to cross in a single direction. $\endgroup$ – Kyle Miller May 26 '18 at 1:36
3
$\begingroup$

Any directed acyclic graph with a finite non-zero number of nodes must have at least one "start node" with no incoming edges and at least one "end node" with no outgoing edges (potentially a node may be both a start node and an end node).

If there are no end nodes then any forward path through the graph can be extended forever. If there are no start nodes then any reverse path through the graph can be extended forever. An infinite length path in a finite size graph clearly must be cyclic.

If there are both start and end nodes then remove them and their associated edges from the graph and go back to the start.

Eventually one of two things will happen.

  1. You will get a graph with no start nodes or with no end nodes, your graph is cyclic.
  2. You eliminate your entire graph, your graph is acyclic.

So for example in this case.

In the initial graph A is a start node and E and F are end nodes.

After removing those nodes we have B, C and D left. B is now both a start node and an end node. C is a start node, D is an end node.

After removing those nodes we have no graph left. So the graph was acyclic.

$\endgroup$
2
$\begingroup$

The adjacency matrix of the graph to the power of the number of vertices is the zero matrix... In particular, all eigenvalues of the adjacency matrix are zero...

$\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.