有向无环图：修订间差异
删除的内容 添加的内容
小 消歧義 |
内容扩充 |
||
| 第3行： | 第3行： | ||
因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。 |
因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。 |
||
== 数学性质 == |
|||
=== 可达性，传递闭包和传递归约 === |
|||
有向无环图的[[可达性]]可以用其顶点的[[偏序关系]]{{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''}}。 |
|||
==应用== |
==应用== |
||
2020年1月14日 (二) 20:26的版本
在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG,directed acyclic graph）。[1]
因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
数学性质
可达性，传递闭包和传递归约
有向无环图的可达性可以用其顶点的偏序关系≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。这也被称作v是从u可达的。[2]不同的有向无环图可以有着相同的可达关系和偏序关系。[3]例如，有两条边a → b，b → c的有向无环图，和有三条边的a → b, b → c，a → c的有向无环图有着相同的偏序关系a ≤ b ≤ c。
应用
参考文献
- ^ Introduction to Algorithms [算法导论]. : 1172. ISBN 978-7-111-40701-0.
- ^ Kozen, Dexter, The Design and Analysis of Algorithms, Monographs in Computer Science, Springer: 9, 1992, ISBN 978-0-387-97687-7.
- ^ Banerjee, Utpal, Exercise 2(c), Loop Transformations for Restructuring Compilers: The Foundations, Springer: 19, 1993, ISBN 978-0-7923-9318-4.