更改

跳到导航 跳到搜索
删除191字节 、 2021年6月2日 (三) 17:47
第17行: 第17行:  
传递约简和传递闭包都是有向无环图的特有概念<!-- is uniquely defined 唯一的? -->。相反的,对于有向有环图,可以存在多个与原图有着相同可达性的最简子图。<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref>
 
传递约简和传递闭包都是有向无环图的特有概念<!-- is uniquely defined 唯一的? -->。相反的,对于有向有环图,可以存在多个与原图有着相同可达性的最简子图。<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref>
   −
[[File:Hasse diagram of powerset of 3.svg|thumb|300px|将{ x, y, z }的[[幂集]]按[[子集|包含]]偏序排序得到的[[哈斯图]]]]
+
对于有向无环图G和表达其可达性的偏序关系≤,它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用,因为它们比其他具有相同偏序关系的图的边数要少,这简化了绘图。偏序关系的[[哈斯图]]由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>
对于有向无环图{{mvar|G}}和表达其可达性的偏序关系{{math|≤}},它的传递规约也可以看作包含{{mvar|G}}的{{link-en|覆盖关系|covering relation}}中每一条边的{{mvar|G}}的子图。传递规约在图示有向无环图的偏序关系时十分有用,因为它们比其他具有相同偏序关系的图的边数要少,这简化了[[绘图]]。偏序关系的[[哈斯图]]由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>
      
=== 拓扑排序===
 
=== 拓扑排序===
387

个编辑

导航菜单