387
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + − 第16行：
第15行： − + +
无编辑摘要
本词条由孙钦贵初步翻译
本词条由孙钦贵初步翻译
[[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|250px|图1：一个有向无环图的例子 Example of a directed acyclic graph]]
[[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|250px|图1：一个有向无环图的例子]]
在图论和计算机科学中，<font color="#ff8000">'''有向无环图 Directed acyclic graph'''</font>（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由<font color="#ff8000"> '''顶点 Vertex''' </font>和<font color="#ff8000"> '''边 Edge''' </font>(也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的<font color="#ff8000"> '''环 Loop''' </font>。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000"> '''拓扑排序 Topologically ordered''' </font>。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。
在图论和计算机科学中，<font color="#ff8000">'''有向无环图 Directed acyclic graph'''</font>（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由<font color="#ff8000"> '''顶点 Vertex''' </font>和<font color="#ff8000"> '''边 Edge''' </font>(也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的<font color="#ff8000"> '''环 Loop''' </font>。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000"> '''拓扑排序 Topologically ordered''' </font>。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。
=== 可达性，传递闭包和传递归约 ===
=== 可达性，传递闭包和传递归约 ===
[[file:A_DAG_G.png|thumb|right|175px|图2：有向无环图G A DAG]] [[file:Transitive_reduction_of_G.png|thumb|right|124px|图3：G的传递规约 Transitive reduction of G]]
[[file:A_DAG_G.png|thumb|right|175px|图2：有向无环图]]
[[file:Transitive_reduction_of_G.png|thumb|right|124px|图3：G的传递规约]]
有向无环图的<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''}}。