387
个编辑
更改
跳到导航
跳到搜索
第16行：
第16行： + + + + + + + 第24行：
第31行： −
→可达性，传递闭包和传递归约
=== 可达性，传递闭包和传递归约 ===
=== 可达性，传递闭包和传递归约 ===
<gallery>
Example.jpg|说明1
Example.jpg|说明2
[[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图2：有向无环图G A DAG G]]
[[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|124px|图3：G的传递规约 Transitive reduction of G]]
</gallery>
有向无环图的<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''}}。
对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的<font color="#ff8000"> '''覆盖关系 Covering relation''' </font>中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的<font color="#ff8000"> '''哈斯图 Hasse diagram''' </font>由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的<font color="#ff8000"> '''哈斯图 Hasse diagram''' </font>由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>
=== 拓扑排序===
=== 拓扑排序===