Editing Directed acyclic graph (section)

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