Editing Directed acyclic graph (section)

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