离散数学_九章：关系 —— 拓扑排序

假设一个项目由20个不同的任务构成。某些任务只能在其他任务结束之后完成。如何找到关于这些任务的顺序？

为了对这个问题建模，我们在任务的集合上构造一个偏序，使得:

a ≺ b iff a 和 b 是任务且直到a结束后b才能开始

（ iff：if and only if，当且仅当）

为安排好这个项目，需要得出与这个偏序相容的所有20个任务的顺序，下面我们说明如何做到这一点

背景知识

相容

如果只要 aRb 就有 a ≼ b，则称一个全序 ≼ 与偏序R是相容的

（回顾一下aRb：表示(a, b)∈R。当(a, b)属于R时，称a与b有关系R）

一个引理

引理：每个有穷非空偏序集 ( S，≼ ) 至少有一个极小元

证明：选择S的一个元素a0 。如果 a0 不是极小元，那么存在元素a1满足a1 ≺ a0。如果 a1 不是极小元，那么存在元素a2 ，满足a2 ≺ a1 ······

（继续这一过程，使得如果 an 不是极小元，那么存在元素 an+1 满足 an+1≺ an 。因为在这个偏序集元素个数有穷，所以这个过程一定会结束并且具有极小元an）

什么是拓扑排序

从一个偏序构造一个相容的全序称为拓扑排序。

❗注意我们这里将要描述的拓扑排序算法对任何有穷非空偏序集都有效

为了在偏序集① (A， ≼ ) 上定义一个全序②，首先选择一个极小元素③a1 ，由上面的引理可知，这样的元素存在。接着，(A - { a1 }， ≼ )也是一个偏序集。如果它是非空的，选择这个偏序集的一个极小元 a2 然后再移出 a2 ，如果还有其他的元素留下来，在 A - { a1 ， a2 } 中选择一个极小元 a3 继续这个过程，只要还有元素留下来，就在 A - { a1 ， a2 ，······，ak } 中选择极小元ak+1

因为A是有穷集，所以这个过程一定会终止。

最终产生一个元素序列a1 ， a2 ，······，an。所需要的全序 ≼t 定义为：a1 ≺t a2 ≺t ······ ≺t an

这个全序与初始偏序相容。

(因为如果在初始偏序中 b ≺ c ，c在算法的某个阶段 b 已经被移出时，被选择为极小元，否则 c 就不是极小元。

*①集合 S 与定义在其上的偏序关系R 一起称为偏序集，记作 (S, R)

②全序：偏序集，且 S 中的每对元素都是可比的；

可比：a,b是集合S中的元素，存在a ≼ b 或 b ≼ a

③极小元素：假设a为极小元（素），则任取与a具有关系R的元素x，都有aRx（a ≼ x，在Hasse图中的表现：汇聚到下部的结点）

拓扑排序算法（伪代码）

procedure topological sort(( S, ≼ ):有穷非空偏序集)
  k:=1
  while S ≠ ∅
  ak := S的极小元
  S := S - {ak}
  k := k+1
return a1, a2, a3, ···, an

(上面的 " ak "： k是下标)

几个实例

例1

📗找出与偏序集( { 1，2，4，5，12，20 }，| )相容的一个全序。

🔴解：

先画出Hasse图：

第一步选择一个极小元，这个元素只能是1（因为1是唯一的极小元）

然后除去我们所选的那个极小元：

下面四种都可以：

例2

📗一个计算机公司的开发项目需要完成7个任务。其中某些任务只能在其他任务结束后才能开始。考虑如下建立任务上的偏序，如果任务 Y 在 X 结束后才能开始，则任务 X < 任务 Y 。这7个任务对应于这个偏序的哈塞图如图所示。求一个任务的执行顺序，使得能够完成这个项目

🔴解：

可以通过执行一个拓扑排序得到7个任务的排序。排序的步骤显示在下面的图中。这个排序的结果，A ≺ C ≺ B ≺ E ≺ F ≺ D ≺ G，给出了一种可行的任务次序。