387
个编辑
更改
跳到导航
跳到搜索
第54行：
第54行： − − − 在这个部分顺序中，两个顶点的顺序与有向无环图中存在从到的有向路径时的顺序完全一致; 也就是说，当从。然而，不同的 DAGs 可能产生相同的可达关系和相同的偏序。例如，有向无环图具有两条边，并且与具有三条边、和的图具有相同的可达性关系。这两种 DAGS 产生相同的偏序，其中顶点的顺序为。 − 第70行：
第66行： − 如果是一个有向无环图，那么它的有向无环传递闭包图就是具有最多边的图，这些边表示相同的可达性关系。它有一个优势，无论何时可以达到。也就是说，可达关系中每一对相关的不同元素都有一个边，因此可以认为是可达关系直接转化为图论术语。同样的将偏序转换为 DAGs 的方法更为普遍: 对于每个有限偏序集，每个成员有一个顶点，每对相关元素有一条边的图是自动传递闭的 DAG，并且具有可达关系。这样，每个有限偏序集都可以表示为一个 DAG 的可达关系。+ 第78行：
第74行： − 有向无环图的传递约简是一个具有最少边的图，它表示的可达性关系与。这是一个子图的，由丢弃的边，其中也包含一个较长的路径连接相同的两个顶点。 第84行：
第79行： − 和传递闭包一样，传递约简也是针对 DAGs 的唯一定义。相反，对于不是无圈的有向图，可以有多个具有相同可达关系的极小子图。+ − 第92行：
第86行： − 如果一个有向无环图具有一个由偏序描述的可达关系，那么它的传递约简就是一个子图，该子图的覆盖关系中的每一对都有一个边。传递约简在可视化它们所表示的部分顺序方面很有用，因为它们比其他表示相同顺序的图有更少的边，从而导致更简单的图绘制。偏序哈斯图是一幅传递归约图，其中每条边的方向通过将边的起始顶点放置在比其终止顶点位置更低的位置来显示。+ − −
→Reachability, transitive closure, and transitive reduction
有向无环图的可达性可以用其顶点的<font color="#ff8000"> 偏序关系</font>≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。也就是，从节点u是可达节点v。[5] 不同的有向无环图可以有着相同的可达关系和偏序关系[6]。例如，有两条边a → b，b → c的有向无环图，和有三条边的a → b, b → c，a → c的有向无环图有着相同的偏序关系a ≤ b ≤ c。
有向无环图的可达性可以用其顶点的<font color="#ff8000"> 偏序关系</font>≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。也就是，从节点u是可达节点v。[5] 不同的有向无环图可以有着相同的可达关系和偏序关系[6]。例如，有两条边a → b，b → c的有向无环图，和有三条边的a → b, b → c，a → c的有向无环图有着相同的偏序关系a ≤ b ≤ c。
If is a DAG, its transitive closure is the graph with the most edges that represents the same reachability relation. It has an edge whenever can reach . That is, it has an edge for every related pair of distinct elements in the reachability relation of , and may therefore be thought of as a direct translation of the reachability relation into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set , the graph that has a vertex for each member of and an edge for each pair of elements related by is automatically a transitively closed DAG, and has as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
If is a DAG, its transitive closure is the graph with the most edges that represents the same reachability relation. It has an edge whenever can reach . That is, it has an edge for every related pair of distinct elements in the reachability relation of , and may therefore be thought of as a direct translation of the reachability relation into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set , the graph that has a vertex for each member of and an edge for each pair of elements related by is automatically a transitively closed DAG, and has as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
对于一个有向无环图G，它的传递闭包等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当u可达v的时候，边u → v必定存在。换句话说，每个G中的非相同元素偏序关系对u ≤ v都在这个图中有一条边。这可以被视作用图来可视化图G的可达性关系。
The transitive reduction of a DAG is the graph with the fewest edges that represents the same reachability relation as . It is a subgraph of , formed by discarding the edges for which also contains a longer path connecting the same two vertices.
The transitive reduction of a DAG is the graph with the fewest edges that represents the same reachability relation as . It is a subgraph of , formed by discarding the edges for which also contains a longer path connecting the same two vertices.
Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.<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>
Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.<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>
Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.
Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.
有向无环图G的传递规约为和其有着相同可达性，边数最少的图。它是G的一个子图。构造方法为当G有着一条更长的路径连接顶点u和v的时候，消去边u → v。 传递约简和传递闭包都是有向无环图的特有概念。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。[7]
If a DAG has a reachability relation described by the partial order , then the transitive reduction of is a subgraph of that has an edge for every pair in the covering relation of . Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler graph drawings. A Hasse diagram of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
If a DAG has a reachability relation described by the partial order , then the transitive reduction of is a subgraph of that has an edge for every pair in the covering relation of . Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler graph drawings. A Hasse diagram of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。[9]
=== Topological ordering ===
=== Topological ordering ===