387
个编辑
更改
跳到导航
跳到搜索
第88行：
第88行： − + 第98行：
第98行： − 有向图的拓扑排序是将其顶点排序成一个序列，这样，对于每一条边，边的起点在序列中出现的时间早于边的终点。一个有拓扑顺序的图不能有圈，因为圈最早点的边必须定向错误。因此，每个具有拓扑序的图都是无循环的。相反，每个有向无环图至少有一个拓扑序。因此，拓扑序的存在可以用作有向无圈图的等价定义: 它们正是具有拓扑序的图。+ 第110行：
第110行： − +
→Topological ordering
对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。[9]
对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。[9]
=== Topological ordering ===
=== Topological ordering 拓扑排序===
{{multiple image|image1=Topological Ordering.svg|caption1=A [[Topological sorting|topological ordering]] of a directed acyclic graph: every [[Edge (graph theory)|edge]] goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.|image2=Transitive Closure.svg|caption2=Adding the red edges to the blue directed acyclic graph produces another DAG, the [[transitive closure]] of the blue graph. For each red or blue edge {{mvar|uv}}, {{mvar|v}} is [[Reachability|reachable]] from {{mvar|u}}: there exists a blue path starting at {{mvar|u}} and ending at {{mvar|v}}.}}
{{multiple image|image1=Topological Ordering.svg|caption1=A [[Topological sorting|topological ordering]] of a directed acyclic graph: every [[Edge (graph theory)|edge]] goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.|image2=Transitive Closure.svg|caption2=Adding the red edges to the blue directed acyclic graph produces another DAG, the [[transitive closure]] of the blue graph. For each red or blue edge {{mvar|uv}}, {{mvar|v}} is [[Reachability|reachable]] from {{mvar|u}}: there exists a blue path starting at {{mvar|u}} and ending at {{mvar|v}}.}}
A topological ordering of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings.
A topological ordering of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings.
有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与顶点在这条路径中出现的顺序相同。[9]
In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.<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>
In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.<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>
The family of topological orderings of a DAG is the same as the family of [[linear extension]]s of the reachability relation for the DAG,<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> so any two graphs representing the same partial order have the same set of topological orders.
The family of topological orderings of a DAG is the same as the family of [[linear extension]]s of the reachability relation for the DAG,<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> so any two graphs representing the same partial order have the same set of topological orders.
有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。
=== Combinatorial enumeration ===
=== Combinatorial enumeration ===