Editing Directed acyclic graph (section)

== Mathematical properties ==
=== Reachability relation, transitive closure, and transitive reduction ===
{{multiple image|image1=Tred-G.svg|width1=175|image2=Tred-Gprime.svg|width2=124|caption1=A DAG|caption2=Its transitive reduction}}
The [[Reachability|reachability relation]] of a DAG can be formalized as a [[partial order]] {{math|≤}} on the vertices of the DAG. In this partial order, two vertices {{mvar|u}} and {{mvar|v}} are ordered as {{math|''u'' ≤ ''v''}} exactly when there exists a directed path from {{mvar|u}} to {{mvar|v}} in the DAG; that is, when {{mvar|u}} can reach {{mvar|v}} (or {{mvar|v}} is reachable from {{mvar|u}}).<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|author-link=Dexter Kozen|publisher=Springer|year=1992|isbn=978-0-387-97687-7|page=9|url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA9}}.</ref> However, different DAGs may give rise to the same reachability relation and the same partial order.<ref>{{citation|title=Loop Transformations for Restructuring Compilers: The Foundations|first=Utpal|last=Banerjee|publisher=Springer|year=1993|isbn=978-0-7923-9318-4|page=19|bibcode=1993ltfr.book.....B|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}.</ref> For example, a DAG with two edges {{math|''u'' → ''v''}} and {{math|''v'' → ''w''}} has the same reachability relation as the DAG with three edges {{math|''u'' → ''v''}}, {{math|''v'' → ''w''}}, and {{math|''u'' → ''w''}}. Both of these DAGs produce the same partial order, in which the vertices are ordered as {{math|''u'' ≤ ''v'' ≤ ''w''}}.

The [[transitive closure]] of a DAG is the graph with the most edges that has the same reachability relation as the DAG. It has an edge {{math|''u'' → ''v''}} for every pair of vertices ({{mvar|u}}, {{mvar|v}}) in the reachability relation {{math|≤}} of the DAG, and may therefore be thought of as a direct translation of the reachability relation {{math|≤}} into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set {{math|(''S'', ≤)}}, the graph that has a vertex for every element of {{mvar|S}} and an edge for every pair of elements in {{math|≤}} is automatically a transitively closed DAG, and has {{math|(''S'', ≤)}} as its reachability relation. In this way, every finite partially ordered set can be represented as a DAG.

[[File:Hasse diagram of powerset of 3.svg|thumb|300px|A [[Hasse diagram]] representing the partial order of set inclusion (⊆) among the subsets of a three-element set]]
The [[transitive reduction]] of a DAG is the graph with the fewest edges that has the same reachability relation as the DAG. It has an edge {{math|''u'' → ''v''}} for every pair of vertices ({{mvar|u}}, {{mvar|v}}) in the [[covering relation]] of the reachability relation {{math|≤}} of the DAG. It is a subgraph of the DAG, formed by discarding the edges {{math|''u'' → ''v''}} for which the DAG also contains a longer directed path from {{mvar|u}} to {{mvar|v}}.
Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref> Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler [[graph drawing]]s. A [[Hasse diagram]] of a partial order is a drawing of the transitive reduction in which the orientation of every edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematics|first=Dieter|last=Jungnickel|publisher=Springer|year=2012|isbn=978-3-642-32278-5|pages=92–93|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92}}.</ref>

=== Topological ordering ===
{{multiple image|image1=Topological Ordering.svg|caption1=A [[Topological sorting|topological ordering]] of a directed acyclic graph: every [[Edge (graph theory)|edge]] goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.|image2=Transitive Closure.svg|caption2=Adding the red edges to the blue directed acyclic graph produces another DAG, the [[transitive closure]] of the blue graph. For each red or blue edge {{math|''u'' → ''v''}}, {{mvar|v}} is [[Reachability|reachable]] from {{mvar|u}}: there exists a blue path starting at {{mvar|u}} and ending at {{mvar|v}}.}}

A [[topological ordering]] of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings.<ref name="bang"/>
In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>

The family of topological orderings of a DAG is the same as the family of [[linear extension]]s of the reachability relation for the DAG,<ref>{{citation|title=A Short Course in Discrete Mathematics|series=Dover Books on Computer Science|first1=Edward A.|last1=Bender|first2=S. Gill|last2=Williamson|publisher=Courier Dover Publications|year=2005|isbn=978-0-486-43946-4|page=142|url=https://books.google.com/books?id=iuEoAwAAQBAJ&pg=PA142|contribution=Example 26 (Linear extensions – topological sorts)}}.</ref> so any two graphs representing the same partial order have the same set of topological orders.

=== Combinatorial enumeration ===
The [[graph enumeration]] problem of counting directed acyclic graphs was studied by {{harvtxt|Robinson|1973}}.<ref name="enum">{{citation|first=R. W.|last=Robinson|contribution=Counting labeled acyclic digraphs|pages=239–273|editor-first=F.|editor-last=Harary|editor-link=Frank Harary|title=New Directions in the Theory of Graphs|publisher=Academic Press|year=1973}}. See also {{citation
|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year =  1973| title = Graphical Enumeration  | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref>
The number of DAGs on {{mvar|n}} labeled vertices, for {{math|1=''n''&nbsp;=&nbsp;0, 1, 2, 3, …}} (without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is
:1, 1, 3, 25, 543, 29281, 3781503, … {{OEIS|id=A003024}}.
These numbers may be computed by the [[recurrence relation]]
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" />
[[Eric W. Weisstein]] conjectured,<ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture|mode=cs2}}</ref> and {{harvtxt|McKay|Royle|Wanless|Oggier|2004}} proved, that the same numbers count the [[Logical matrix|(0,1) matrices]] for which all [[eigenvalue]]s are positive [[real number]]s. The proof is [[bijective proof|bijective]]: a matrix {{mvar|A}} is an [[adjacency matrix]] of a DAG if and only if {{math|''A''&nbsp;+&nbsp;''I''}} is a (0,1) matrix with all eigenvalues positive, where {{mvar|I}} denotes the [[identity matrix]]. Because a DAG cannot have [[Loop (graph theory)|self-loops]], its adjacency matrix must have a zero diagonal, so adding {{mvar|I}} preserves the property that all matrix coefficients are 0 or 1.<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay (mathematician)|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|page=33|arxiv=math/0310423|bibcode=2004JIntS...7...33M|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>

=== Related families of graphs ===
{{multiple image
|image1=Butterfly multitree.svg|caption1=A [[multitree]], a DAG in which the subgraph reachable from any vertex induces an undirected tree (e.g. in red)
|image2=Polytree.svg|caption2=A [[polytree]], a DAG formed by orienting the edges of an undirected tree
}}
A ''[[multitree]]'' (also called a ''strongly unambiguous graph'' or a ''mangrove'') is a DAG in which there is at most one directed path between any two vertices. Equivalently, it is a DAG in which the subgraph reachable from any vertex induces an [[Tree (graph theory)|undirected tree]].<ref>{{citation
 | last1 = Furnas | first1 = George W. | author1-link = George Furnas
 | last2 = Zacks | first2 = Jeff
 | contribution = Multitrees: enriching and reusing hierarchical structure
 | doi = 10.1145/191666.191778
 | pages = 330–336
 | title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
 | year = 1994| isbn = 978-0897916509 | s2cid = 18710118 | doi-access = free}}.</ref>

A ''[[polytree]]'' (also called a ''directed tree'') is a multitree formed by orienting the edges of an undirected tree.<ref>{{citation
 | last1 = Rebane
 | first1 = George
 | last2 = Pearl
 | first2 = Judea
 | author2-link = Judea Pearl
 | contribution = The recovery of causal poly-trees from statistical data
 | pages = 222–228
 | title = Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
 | url = http://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf
 | year = 1987
 }}.</ref>

An ''[[Arborescence (graph theory)|arborescence]]'' is a polytree formed by [[Orientation (graph theory)|orienting]] the edges of an undirected tree away from a particular vertex, called the ''root'' of the arborescence.