更改

=== 可达性，传递闭包和传递归约 ===

=== 可达性，传递闭包和传递归约 ===

有向无环图的[[可达性]]可以用其顶点的<font color="#ff8000"> 偏序关系Partial order</font>{{math|≤}}来表示。在偏序关系中，如果存在一条路径从顶点{{mvar|u}}指向顶点{{mvar|v}}，它们的偏序关系可被写作{{math|''u'' ≤ ''v''}}。这也被称作{{mvar|v}}是从{{mvar|u}}可达的。<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|authorlink=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>不同的有向无环图可以有着相同的可达关系和偏序关系。<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|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}.</ref>例如，有两条边{{math|''a'' → ''b''}}，{{math|''b'' → ''c''}}的有向无环图，和有三条边的{{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}，{{math|''a'' → ''c''}}的有向无环图有着相同的偏序关系{{math|''a'' ≤ ''b'' ≤ ''c''}}。

有向无环图的<font color="#ff8000">可达性Reachability</font>可以用其顶点的<font color="#ff8000">偏序关系Partial order</font>{{math|≤}}来表示。在偏序关系中，如果存在一条路径从顶点{{mvar|u}}指向顶点{{mvar|v}}，它们的偏序关系可被写作{{math|''u'' ≤ ''v''}}。这也被称作{{mvar|v}}是从{{mvar|u}}可达的。<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|authorlink=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>不同的有向无环图可以有着相同的可达关系和偏序关系。<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|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}.</ref>例如，有两条边{{math|''a'' → ''b''}}，{{math|''b'' → ''c''}}的有向无环图，和有三条边的{{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}，{{math|''a'' → ''c''}}的有向无环图有着相同的偏序关系{{math|''a'' ≤ ''b'' ≤ ''c''}}。

对于一个有向无环图{{mvar|G}}，它的<font color="#ff8000">传递闭包Transitive closure</font>等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当{{mvar|u}}可达{{mvar|v}}的时候，边{{math|''u'' → ''v''}}必定存在。换句话说，每个{{mvar|G}}中的非相同元素<!-- distinct elements -->偏序关系对{{math|''u''&nbsp;≤&nbsp;''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。

对于一个有向无环图{{mvar|G}}，它的<font color="#ff8000">传递闭包Transitive closure</font>等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当{{mvar|u}}可达{{mvar|v}}的时候，边{{math|''u'' → ''v''}}必定存在。换句话说，每个{{mvar|G}}中的非相同元素<!-- distinct elements -->偏序关系对{{math|''u''&nbsp;≤&nbsp;''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。

有向无环图{{mvar|G}}的[[传递规约]]为和其有着相同可达性，边数最少的图。它是{{mvar|G}}的一个子图。构造方法为当{{mvar|G}}有着一条更长的路径连接顶点{{mvar|u}}和{{mvar|v}}的时候，消去边{{math|''u'' → ''v''}}。

有向无环图{{mvar|G}}的<font color="#ff8000">传递规约Transitive reduction</font>为和其有着相同可达性，边数最少的图。它是{{mvar|G}}的一个子图。构造方法为当{{mvar|G}}有着一条更长的路径连接顶点{{mvar|u}}和{{mvar|v}}的时候，消去边{{math|''u'' → ''v''}}。

传递约简和传递闭包都是有向无环图的特有概念<!-- is uniquely defined 唯一的？ -->。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。<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>

传递约简和传递闭包都是有向无环图的特有概念<!-- is uniquely defined 唯一的？ -->。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。<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>

对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的[[哈斯图]]由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>

对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的<font color="#ff8000">覆盖关系Covering relation</font>中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的[[哈斯图]]由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>

=== 拓扑排序===

=== 拓扑排序===