387
个编辑
更改
跳到导航
跳到搜索
第20行：
第20行： − +
→可达性，传递闭包和传递归约
有向无环图的<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''}}。
有向无环图的<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''}}。
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图4：将{ x, y, z }的幂集按包含偏序排序得到的哈斯图]]
[[file:A_Hasse_diagram_representing_the_partial_order.png|thumb|right|175px|图4：将{ x, y, z }的幂集按包含偏序排序得到的哈斯图]]
对于一个有向无环图{{mvar|G}}，它的<font color="#ff8000"> '''传递闭包 Transitive closure''' </font>等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当{{mvar|u}}可达{{mvar|v}}的时候，边{{math|''u'' → ''v''}}必定存在。换句话说，每个{{mvar|G}}中的非相同元素<!-- distinct elements -->偏序关系对{{math|''u'' ≤ ''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。
对于一个有向无环图{{mvar|G}}，它的<font color="#ff8000"> '''传递闭包 Transitive closure''' </font>等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当{{mvar|u}}可达{{mvar|v}}的时候，边{{math|''u'' → ''v''}}必定存在。换句话说，每个{{mvar|G}}中的非相同元素<!-- distinct elements -->偏序关系对{{math|''u'' ≤ ''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。