2.7 偏序关系
本章目录 · 1 节
本章导读
定义2.7.1:非空集合 上自反、反对称且传递的关系称为偏序关系,通常记作 。写 表示 属于该关系;读作“小于或等于”时,指的是指定顺序,不一定是数值大小。集合与其偏序一起组成偏序集,记为 (定义2.7.4)。
例如,整数集上的通常 、集合幂集 上的 、正整数集上的整除关系都是偏序。整除偏序中 表示 ;也可以用 给实数排序,此时 表示 ,不要把抽象顺序与通常的 混为一谈。整除关系的底集必须说明:若把正、负整数一起纳入,则 且 ,但 ,不满足反对称性,不能照搬正整数上的结论。恒等关系 总是偏序;全域关系 只有在非空 为单元素集时才是偏序。
定义2.7.2:在偏序集中, 表示 且 ;若 或 ,称 可比。两个不同元素可能一个严格在前,也可能不可比。例如 上按整除排序,有 、,但2与3不可比。不可比表示两个方向都不成立,不表示二者相等。
定义2.7.3:任意两个元素均可比的偏序称为全序或线序。通常数值大小顺序是全序;整除顺序一般不是全序。全序必为偏序,偏序不一定为全序。
定义2.7.5:若 ,且不存在 使 ,称 覆盖 。例如 的整除偏序中,2覆盖1,4和6覆盖2;4不覆盖1,因为中间有2;6也不覆盖4,因为4不整除6。
有限偏序集的哈斯图只画覆盖边:去掉自环,省去由传递性得到的边,把较小元素放在下方,以无箭头线段连接覆盖对。自反有序对及沿向上路径得到的传递有序对仍属于原关系,只是在图上不重复画出。两条线相交而未标顶点时,交点不是元素,也不能借交点改变路径。有限性很重要:有理数通常顺序中不存在覆盖对,不能仅凭覆盖边恢复整个无限偏序。
【例2.7.1】画出 上整除偏序,以及 上包含偏序的哈斯图。
解:整除图中,1的直接上邻点为2、3、5、7;2的直接上邻点为4、6;3的直接上邻点为6、9;4的直接上邻点为8。不要把 等已有中间元素的关系再画成覆盖边。
幂集图按子集的元素个数分四层。若 ,且 恰比 多一个元素, 就覆盖 。底层为 ,顶层为 ,共有8个顶点和12条覆盖边。
【例2.7.2】由图2.7.2写出底集和完整关系。
解:。覆盖边给出 ;传递性还要求 ,自反性要求全部 。所以
完整关系有17个有序对,不能只把图中的7条线当成完整关系。
定义2.7.6:设 ,并且 。若对全部 都有 ,则 是 的最小元;若全部 ,则是最大元。若 中没有严格小于 的元素,称 为极小元;若没有严格大于 的元素,称为极大元。
最小元必须与 的所有元素可比并排在它们之前,极小元只要求没有更小者。最小元、最大元若存在就唯一;极小元、极大元可能有多个。每个非空有限偏序集都有极小元和极大元;若非空有限 只有一个极小元,它就是最小元,极大元也类似。不能去掉“非空有限”的条件:无限下降链未必有极小元;把一个孤立点与一条无最小元的无限链并在一起,可有唯一极小元却没有最小元。
【例2.7.3】求图2.7.2所示整个底集的极小元、最小元、极大元和最大元。
解:极小元为 ,极大元为 ,没有最小元和最大元。孤立点 既极小也极大,但它与其他元素不可比,所以既不是全体元素的最小元也不是最大元。
【例2.7.4】设有限集合 满足 ,,按包含关系排序,讨论其最小元、最大元、极小元和极大元。
解:条件保证 。最小元、最大元均不存在。任意不同的单元素子集互不可比,而每个非空子集包含某个单元素子集,所以极小元恰为全部 ,。极大元恰为全部 ,:它们只需再加一个元素就成为已被删去的 ,而更小的真子集还可以向上扩张。当 时,两种极端元素恰好都是那两个单元素子集,但仍没有唯一的最小元或最大元。
定义2.7.7:设 。若 且对全部 有 ,称 为 的上界;若全部 ,称为下界。这里界只须属于环境底集 ,不一定属于 。全体上界组成的集合若有最小元,称为 的最小上界或上确界;全体下界若有最大元,称为最大下界或下确界。
最小元一定是下确界,最大元一定是上确界;反过来需要确界确实属于 才能成立。确界若存在就唯一;存在上界不保证有上确界,存在下界不保证有下确界。界和极值均须相对于指定的环境偏序集讨论,换了底集可能改变结论。
在图2.7.2中取 ,上界为 ,上确界为 ;没有共同下界,因而没有下确界。取 时,上界有 ,其中 不可比,所以虽有上界却没有上确界。这也说明“极小上界”不等于“最小上界”。
任务调度是偏序关系的应用。给定非空有限任务集 和 台相同机器; 表示 必须先完成, 才能开始。每个任务占一台机器,执行后不中断,耗时 ,截止时间 ;以 表示开始时刻,最终完成时间为 。可行调度应同时满足
第一项约束截止时间;第二项限制同时执行的任务数,区间取左闭右开,允许一个任务结束时立刻开始下一个;第三项约束先后顺序。目标是在所有可行调度中使 最小。任务可安排在任一机器,不能仅满足先后关系而忽略机器容量。
【例2.7.5】两台机器执行六个任务,截止时间均为7,耗时依次为 。前驱约束及书中的两个调度如下。
直接约束为 ,并包含传递推出的先后关系。
解:方案一中,机器1依次执行 ,机器2执行 。方案二中,机器1执行 ,机器2执行 。两者均满足所有前驱、容量及截止时间约束。因为链 的总耗时为 ,任何调度都有 ,方案二达到下界,因而最优。只算总工作量得到 ,未考虑前驱关系,不能据此断言4个时间单位可以完成。
当只有一台机器且没有截止限制时,可以用拓扑排序安排任务。有限偏序的拓扑排序是在不违反已有先后关系的前提下,把所有元素排列成一个全序;等价地,把严格偏序扩充成严格全序。已有有序对必须保留,原本不可比的元素可能有不同排列。算法可以反复取尚未删除的极小元,输出后删除,再继续;有限偏序必能完成这一过程。
例如图中的 与 不可比,不同的拓扑排序可以先选 ,也可以先选 ;但绝不能把 放在其前驱 或 之前。拓扑排序解决的是前驱约束下的线性排列,不能把任意拓扑序直接当作多机器带截止约束问题的最优调度。
