更改

有向无环图 Directed acyclic graph (查看源代码)

2021年6月14日 (一) 11:38的版本

删除42字节、 2021年6月14日 (一) 11:38

无编辑摘要

第1行：第1行：

[[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|250px|图1：一个有向无环图的例子]]

−

在图论和计算机科学中，'''有向无环图 Directed acyclic graph'''（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由 '''顶点 Vertex''' 和 '''边 Edge''' ~~(也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向~~ 不会形成一个闭合的 '''环 Loop''' 。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成 '''拓扑排序 Topologically ordered''' 。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。

+

在图论和计算机科学中，'''有向无环图 Directed acyclic graph'''（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由 '''顶点 Vertex''' 和 '''边 Edge''' （也称为弧）组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向不会形成一个闭合的 '''环 Loop''' 。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成 '''拓扑排序 Topologically ordered''' 。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。

−

第12行：第11行：

当存在一条从顶点{{mvar|u}}到顶点{{mvar|v}}的路径时，顶点v被称作是从顶点{{mvar|u}} '''可达的 Reachability''' 。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条 非平凡路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。<ref>{{citation|title=Simulation Techniques for Discrete Event Systems|volume=14|series=Cambridge Computer Science Texts|first=I.|last=Mitrani|year=1982|publisher=Cambridge University Press|isbn=9780521282826|page=27|url=https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27}}.</ref>

−

== 数学性质 ==

+

==数学性质==

−

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

+

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

[[file:A_DAG_G.png|thumb|right|175px|图2：有向无环图]]

[[file:Transitive_reduction_of_G.png|thumb|right|124px|图3：有向无环图G的传递规约]]

第28行：第27行：

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

−

=== 拓扑排序===

+

===拓扑排序===

−

有向无环图的 '''拓扑排序 Topological ordering''' 为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang"/>基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>

+

有向无环图的 '''拓扑排序 Topological ordering''' 为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang" />基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>

有向无环图的拓扑排序族等同于其可达性的 '''线性拓展 Linear extension''' 族。 <ref>{{citation|title=A Short Course in Discrete Mathematics|series=Dover Books on Computer Science|first1=Edward A.|last1=Bender|first2=S. Gill|last2=Williamson|publisher=Courier Dover Publications|year=2005|isbn=978-0-486-43946-4|page=142|url=https://books.google.com/books?id=iuEoAwAAQBAJ&pg=PA142|contribution=Example 26 (Linear extensions – topological sorts)}}.</ref>因此，偏序关系相同的任意两个图会有相同的拓扑排序集。

−

=== 组合计数 ===

+

===组合计数===

罗宾逊 Robinson (1973) 研究了有向无环图的 '''图计数 Graph enumeration''' 问题。<ref name="enum">{{citation|first=R. W.|last=Robinson|contribution=Counting labeled acyclic digraphs|pages=239–273|editor-first=F.|editor-last=Harary|editor-link=Frank Harary|title=New Directions in the Theory of Graphs|publisher=Academic Press|year=1973}}. See also {{citation

|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref>

第43行：第42行：

埃里克·韦斯坦因 Eric W. Weisstein <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>，{{mvar|n}}个顶点的标号有向无环图的数量与其中所有 '''特征值 Eigenvalues''' 都为正实数的{{math|n*n}} '''逻辑矩阵''' 的数量相同。这一点随后被 McKay 证实，证明采用了 '''双射法 Bijective'''：一个矩阵{{mvar|A}}是有向无环图的一个 '''邻接矩阵 Adjacency matrix''' ，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为 '''单位矩阵 Identity matrix''' 。因为一个有向无环图不允许 '''自环 Self-loops''' ，它的邻接矩阵的对角线必定全为0。因此，加上{{mvar|I}}保持了所有矩阵因子都是0或1的特性。<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>

−

=== 相关概念 ===

+

===相关概念===

[[file:A_polytree.png|thumb|right|175px|图7：多重树，一种由无向树的边定向而成的有向无环图]]

[[file:A_multitree.png|thumb|right|124px|图8：多重树，是一种DAG，其中每个从一个顶点（红色）可到达的子图都是一棵树]] '''多重树 Polytree''' 由将自由树的边 '''定向 Orienting''' 而得到。<ref>{{citation

第68行：第67行：

| year = 1994| isbn = 978-0897916509 }}.</ref>

−

== 相关计算问题 ==

+

==相关计算问题==

−

=== 基于邻接矩阵的有向无环图的判别方法 ===

+

===基于邻接矩阵的有向无环图的判别方法===

'''定理'''：

对于邻接矩阵 <math> B\in \left\{ 0, 1 \right\}^{d*d} </math>， <math> B </math>是有向无环图当且仅当

−

: <math> tr(e^B)=d</math>

+

:<math> tr(e^B)=d</math>

依据泰勒展开公式 <math> e^B=I+\sum_{k=1}^{\infty}\,\frac{1}{K!}B^k</math>，有

第81行：第80行：

:<math> B_{ij}^2=\sum_kB_{ik}B_{kj}</math>

−

=== 拓扑排序和识别 ===

+

===拓扑排序和识别===

−

+

可以用 '''线性时间复杂度''' 的卡恩算法来找到一个有向无环图的拓扑排序。<ref name="clrs">{{Introduction to Algorithms|edition=2}} Section 22.4, Topological sort, pp. 549–552.</ref>简单来说，开设一个存放结果的列表{{mvar|L}}，先将入度为零的节点放到{{mvar|L}}中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在{{mvar|L}}中了，所以也可以从末端插入{{mvar|L}}。重复上述操作，直到找不到入度为零的节点。<ref name="j50" /> 另外一种构造拓扑排序的算法是将 '''深度优先搜索''' 的 '''后序遍历''' 结果翻转。<ref name="clrs" />

检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。<ref>For [[深度优先搜索|depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> 对于卡恩算法在内的部分拓扑排序算法，通过在算法终止时判断是否满足一定条件即可知道图是否有环。<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>如果有环，卡恩算法最终获得的{{mvar|L}}中节点个数会与图的节点总数不同。

−

=== 从其他图构建===

+

===从其他图构建===

任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的 '''全序关系 Total order''' ，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是定向方法中的 '''无环定向 Acyclic orientation''' 。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}。如果定义{{mvar|χ}}为给定图的 '''色多项式 Chromatic polynomial''' ，无环定向数量等于{{math|{{!}}''χ''(−1){{!}}}}。<ref>{{citation|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref>

第93行：第92行：

任意有环有向图都可以被转化为有向无环图。只要从图中移除 '''反馈节点集 Feedback vertex set''' 或 '''反馈边集 Feedback arc set''' ，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是 '''NP困难 NP-hard''' 问题。<ref>{{citation | last1=Garey | first1=Michael R. | authorlink1=Michael Garey | last2=Johnson | first2=David S. | authorlink2=David S. Johnson | year=1979| title=[[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]]| publisher=[[W. H. Freeman and Company|W. H. Freeman]]| isbn=0-7167-1045-5| chapter = Problems GT7 and GT8| pages = 191–192}}</ref> 另外一种方法将有环有向图去环的方法是将每个强连通分量[[边收缩|收缩]]为一个顶点。<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> 对于无环图，它的最小反馈顶点或边集为 '''空集''' ，它的强连通分量则为自身。

−

=== 传递闭包和传递约简 ===

+

===传递闭包和传递约简===

有向无环图的传递闭包可以通过 '''广度优先搜索''' 或 '''深度优先搜索''' 对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用 '''矩阵乘法算法 Matrix multiplication algorithm''' 中最快的 '''Coppersmith–Winograd算法'''，其复杂度为{{math|''O''(''n''''2.3728639'')}}。这个算法理论上在 '''稠密图 Dense graph'''中快过{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>

不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的 '''渐进时间复杂度 Asymptotic computational complexity''' 中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>

−

=== 闭包问题 ===

+

===闭包问题===

闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。 '''闭包问题 Closure problem''' 是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作 '''最大流问题''' 的简化版，在 '''多项式时间''' 内被解决。实际上，是否有环对于找到闭包没有影响。<ref>{{citation

| last = Picard | first = Jean-Claude

第110行：第109行：

| year = 1976}}.</ref>

−

=== 最短或最长路径问题 ===

+

===最短或最长路径问题===

基于拓扑排序的性质，有向无环图的[[最短路问题 Shortest paths]]和[[最长路径问题 Longest paths]]可以在线性时间内解决。将顶点拓扑排序后，从前到后遍历每一个顶点，对于遍历到的顶点，更新其所有出边所到达顶点的长度值。如果求最短路，则在本边是更短路径的一部分时更新。求最长路则反之。<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref>对于非有向无环图，最短路需要用复杂度为<math>O(|E|+|V|\log|V|)</math>的 '''戴克斯特拉算法 Dijkstra's algorithm''' 或<math>O (|V| |E|)</math>的 '''贝尔曼-福特算法 Bellman–Ford algorithm''' 等。<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref>最长路径则是一个[[NP困难|NP困难问题]]。<ref>Cormen et al. 2001, p. 966.</ref>

==应用==

−

=== 调度 ===

+

===调度===

有向无环图的偏序关系可以在调度上有着先后顺序限制的系统任务中发挥作用。<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>调度问题的一个重要种类是串联需要更新的对象，如[[电子计算表]]中某个单元格的计算公式依赖于其他单元格，或在程序的[[源代码]]被修改后重新编译[[目标代码|目标文件]]。 '''依赖图 Dependency graph''' 则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为 '''环状依赖 Circular dependency''' 。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 }}.</ref>

第122行：第121行：

[[计划评审技术]]是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑 (项目管理) Milestone (project management)，每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的[[最长路径问题|最长路径]]即为项目的[[关键路径]]。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>

−

=== 数据处理网络 ===

+

===数据处理网络===

有向无环图可以用于表示处理数据的元素网络。在网络中，数据从一个元素顶点的入边进入，处理后从出边离开。

第131行：第130行：

在[[编译器]]中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行 '''通用子表达式删除 Common subexpression elimination''' ，使得代码更高效。<ref>{{citation|title=Advanced Backend Optimization|first1=Sid|last1=Touati|first2=Benoit|last2=de Dinechin|publisher=John Wiley & Sons|year=2014|isbn=978-1-118-64894-0|page=123|url=https://books.google.com/books?id=nO2-AwAAQBAJ&pg=PA123}}.</ref>

−

=== 因果结构 ===

+

===因果结构===

第138行：第137行：

举例来说，'''贝叶斯网络 Bayesian network''' 表示多个概率事件的关联网络。顶点表示事件，后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。<ref>{{citation|title=Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks|publisher=Society for Industrial and Applied Mathematics|first1=Ilya|last1=Shmulevich|first2=Edward R.|last2=Dougherty|year=2010|isbn=978-0-89871-692-4|page=58|url=http://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref>在此基础上，一个有向无环图的 '''端正图 Moral graph''' 通过以下方法而得到：将单个顶点的所有父节点之间添加一条无向边，再将所有的有向边换成无向边。<ref>{{citation |last1= Cowell |first1= Robert G. |author2-link=Philip Dawid|last2=Dawid|first2=A. Philip|author3-link=Steffen Lauritzen|last3=Lauritzen|first3=Steffen L.|author4-link=David Spiegelhalter|last4=Spiegelhalter|first4=David J.|title= Probabilistic Networks and Expert Systems |publisher= Springer |year= 1999 |isbn= 0-387-98767-3 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref>

−

另外一种具有相似因果结构的图是 '''影响图 Influence diagram''' 。其顶点表示决策或不确定的事件，边表示两个顶点之间的因果关系。<ref>{{citation|title=The Technology Management Handbook|first=Richard C.|last=Dorf|publisher=CRC Press|year=1998|isbn=978-0-8493-8577-3|page=9-7|url=http://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref>在流行病学中，这些表示因果关系的图表常常用来评估不同干预手段的效果。<ref>{{citation|title=Encyclopedia of Epidemiology, Volume 1|first=Sarah|last=Boslaugh|publisher=SAGE|year=2008|isbn=978-1-4129-2816-8|page=255|url=http://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name=pearl:95>{{cite journal|last1=Pearl|first1=Judea|authorlink= Judea Pearl|title=Causal diagrams for empirical research|journal=Biometrika|date=1995|volume=82|issue=4|pages=669–709|doi=10.1093/biomet/82.4.669}}</ref>

+

另外一种具有相似因果结构的图是 '''影响图 Influence diagram''' 。其顶点表示决策或不确定的事件，边表示两个顶点之间的因果关系。<ref>{{citation|title=The Technology Management Handbook|first=Richard C.|last=Dorf|publisher=CRC Press|year=1998|isbn=978-0-8493-8577-3|page=9-7|url=http://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref>在流行病学中，这些表示因果关系的图表常常用来评估不同干预手段的效果。<ref>{{citation|title=Encyclopedia of Epidemiology, Volume 1|first=Sarah|last=Boslaugh|publisher=SAGE|year=2008|isbn=978-1-4129-2816-8|page=255|url=http://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name="pearl:95">{{cite journal|last1=Pearl|first1=Judea|authorlink= Judea Pearl|title=Causal diagrams for empirical research|journal=Biometrika|date=1995|volume=82|issue=4|pages=669–709|doi=10.1093/biomet/82.4.669}}</ref>

−

=== 系谱学和版本历史 ===

+

===系谱学和版本历史===

[[File:Family_tree_of_the_Ptolemaic_dynasty.jpeg|thumb|upright=1.5|图11：[[托勒密王朝]]的谱系图。]]

第170行：第169行：

在[[计算几何]]领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在 '''德劳内三角化 Delaunay triangulation''' 的随机增量算法中，在添加每个点时，通过用三个较小的三角形替换一个三角形，以及通过“翻转”操作将三角形对替换为另一对三角形，来改变三角剖分。在该算法的历史有向无环图中，每个在算法中构建出的三角形对应一个顶点，边则将每个三角形和替代它的两个或三个三角形连接起来。这种图结构可以高效地处理 '''点定位 Point location''' 问题，即对于一个查询点{{mvar|q}}，找到它在德勞內三角剖分中的位置。在历史有向无环图中，从起点开始，不断移动到包含{{mvar|q}}的替代三角形组，最后到达的终点必定代表包含q的德劳内三角形。<ref>{{citation|title=Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures|volume=152|series=Mathematical surveys and monographs|first1=János|last1=Pach|author1-link=János Pach|first2=Micha|last2=Sharir|author2-link=Micha Sharir|publisher=American Mathematical Society|isbn=978-0-8218-7533-9|pages=93–94|url=https://books.google.com/books?id=-fguzNaYoqcC&pg=PA93}}.</ref>

−

=== 引用图 ===

+

===引用图===

在 '''引用图 Citation graph''' 中，每个顶点代表单篇著作，边代表著作之间的[[參考文獻|引用]]关系。1965年[[德瑞克·约翰·德索拉·普莱斯|普莱斯]]的文章“科学文献的网络”是使用引用图的一个经典例子。<ref>{{citation | last = Price | first = Derek J. de Solla | date = July 30, 1965 | doi = 10.1126/science.149.3683.510 | issue = 3683 | journal = [[科学 (期刊)|Science]] | pages = 510–515 | pmid = 14325149 | title = Networks of Scientific Papers | url = http://garfield.library.upenn.edu/papers/pricenetworks1965.pdf | volume = 149| bibcode = 1965Sci...149..510D }}.</ref>在引用图中，每篇论文的 '''引用影响（引用次数） Citation impact''' 为对应顶点的入度。这是[[引文分析]]中的一种重要的展示方式。另一个例子是[[裁判 (法律)|法律裁判]]中，法官通过引用过往案例中的判决来支持他们的结论。引用图亦可以用来描绘[[专利]]，因为专利必须要提及[[现有技术]]，即已经公开的并且和本专利有关的先前专利。

相较于[[网络科学]]中对一般图的研究，有向无环图的独特性质可以被用来作深层次分析。例如，传递规约可以呈现引用在不同应用领域的分布情况，这突出了不同领域中不同的引用网构造机制。<ref>{{citation | last1 = Clough | first1 = James R. | last2 = Gollings | first2 = Jamie | last3 = Loach | first3 = Tamar V. | last4 = Evans | first4 = Tim S. | doi = 10.1093/comnet/cnu039 | issue = 2 | journal = Journal of Complex Networks | pages = 189–203 | title = Transitive reduction of citation networks | volume = 3| arxiv = 1310.8224 | year = 2015 }}.</ref>引用图的衍生概念还有 '''主干道路分析 Main path analysis''' ，即对引用图中最显著的一条路径的分析。

−

=== 数据压缩 ===

+

===数据压缩===

[[Image:分别用trie（左）和有向无环词图（右）存放英文单词.png|thumb|right|250px|图12：分别用trie（左）和有向无环词图（右）存放英文单词“tap”，“taps”，“top”和“tops”。<tt>EOW</tt>表示单词结束。]]

有向无环图也可以用于对一系列序列的[[数据压缩|压缩]]中。在这里，有向无环图中的路径代表这些序列。当多个序列有共同的子序列时，子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列，这种方法占用更少空间。例如， '''无环确定有限状态自动机 Deterministic acyclic finite state automaton''' 为仅含单个源（入度为0的顶点）的有向无环图，其每条边附有一个或多个字符。每条其源到汇（出度为0的节点）的路径均代表一个[[字符串]]，字符串可以是英文单词。<ref>{{citation | first1=Maxime | last1=Crochemore | first2=Renaud | last2=Vérin | contribution=Direct construction of compact directed acyclic word graphs | series=Lecture Notes in Computer Science | publisher=Springer | title=Combinatorial Pattern Matching | volume=1264 | year=1997 | pages=116–129 | doi=10.1007/3-540-63220-4_55 | isbn=978-3-540-63220-7 | citeseerx=10.1.1.53.6273 }}.</ref>与其结构不同但功能相似的树称为[[trie]]。相比于trie，有向无环词图允许多条边指向同一个顶点，使得具有相同后缀的一些词的词头可以被相同的顶点所表示，因而更省空间。<ref>{{citation|title=Applied Combinatorics on Words|volume=105|series=Encyclopedia of Mathematics and its Applications|first=M.|last=Lothaire|authorlink=M. Lothaire|publisher=Cambridge University Press|year=2005|isbn=9780521848022|page=18|url=https://books.google.com/books?id=fpLUNkj1T1EC&pg=PA18}}.</ref>

薄荷

7,129

个编辑

更改

有向无环图 Directed acyclic graph (查看源代码)

2021年6月14日 (一) 11:38的版本

导航菜单

搜索