387
个编辑
更改
跳到导航
跳到搜索
第27行：
第27行： − − − − 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.
→拓扑排序
有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与顶点在这条路径中出现的顺序相同。[9]
有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与顶点在这条路径中出现的顺序相同。[9]
有向无环图的拓扑序族与有向无环图的可达关系的线性扩张族相同，因此任意两个表示相同偏序的图具有相同的拓扑序集。
有向无环图的拓扑序族与有向无环图的可达关系的线性扩张族相同，因此任意两个表示相同偏序的图具有相同的拓扑序集。
有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。
有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。