# Directed Acyclic Graph **A [[Graph#Directed graph|directed graph]] that does not have any [[Cycle|cycles]].** ![[DirectedAcyclicCyclicGraph.svg|600]] A **directed acyclic graph** is a graph with directed edges that contains *no directed cycles*, that is, there exists no [[path]] in the graph where the start and end vertices are equal. A directed graph is a directed acyclic graph *if any only if* it can be [[Topological Sorting|topologically sorted]]. Any arbitrary directed graph can be *condensed* into a directed acyclic graph, known as its [[Strongly Connected Component#Condensation graph|condensation graph]], by applying [[Graph Condensation#Vertex Contraction|vertex contraction]] on its [[Strongly Connected Component|strongly connected components]]. ![[CondensationGraph.svg|500]] ## Enumeration The number of directed acyclic graphs of $n$ labelled vertices not limited by their order in topological sorting can be calculated using the [[Binomial Theorem#Binomial coefficient|binomial coefficient]] in a recurrence relation. $a_{n}=\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}2^{k(n-k)}a_{n-k}$