1、5.6 偏序,5.6 偏序,5.6.1引言,请判断上述关系具备哪些性质？,自反、对称、传递,自反、反对称、传递,Def 对于集合A上的关系R，若R具有自反、反对称和传递性，则称R为偏序关系。（A，R）称为偏序集。,5.6.1引言,eg,5.6.1引言,若(a,b)偏序R，则称a“小于等于”b，记作ab。,对偏序R，若ab或ba，则称a和b是可比的。,2和4是可比的，3和5是不可比的,Def 对于集合A上的关系R，若R具有自反、反对称和传递性，则称R为偏序关系。（A，R）称为偏序集。,5.6.1引言,对偏序R，若其每对元素都是可比的，则称R为全序或线序(链)。,对集合S上的偏序R，若R是全序且S
2、的每个非空子集都有最小元素，则称R为良序。,负整数集是Z的子集，却没有最小元。,Def 对于集合A上的关系R，若R具有自反、反对称和传递性，则称R为偏序关系。（A，R）称为偏序集。,5.6.1引言,例：数学归纳法,5.6.1引言,字典中的字按照字母顺序或字典顺序排列，字典顺序是以字母表中的字母顺序为基础的。 即从一个集合上的偏序构造一个集合上的串的序。,5.6 偏序,Def 字典顺序,5.6.2字典顺序,推广到n个偏序的字典顺序,5.6.2字典顺序,5.6 偏序,5.6.3哈塞图,5.6.3哈塞图,去掉环,5.6.3哈塞图,去掉可以通过传递连接的点之间的边,5.6.3哈塞图,现在箭头都是向上的
3、，故去掉箭头,5.6.3哈塞图,包含了足够的信息，称为哈塞图,5.6.3哈塞图,5.6 偏序,5.6.4极大元与极小元,5.6.4极大元与极小元,5.6.4极大元与极小元,5.6.4极大元与极小元,5.6 偏序,若一个偏序的每对元素都有最小上界和最大下界，则称其为格。例如例25信息流模型（自学）,5.6 偏序,在项目安排中有应用,5.6.6拓扑排序,假设一个项目由6个子任务构成，某些任务只能在其他某些任务结束后才能完成，则R=(x ,y)| x需在y之前完成为偏序，其哈塞图如下？如何找到这些任务之间的顺序？（假设是流水线作业，即每个时间段只能完成一个任务）,偏序,全序,称此全序与偏序是相容的，称为其拓扑排序,5.6.6拓扑排序,偏序的拓扑排序不唯一。如何构造？,一句话描述其算法思路：即每次在剩余的偏序中选取极小元素后删除极小元素即可。（见板书）,掌握偏序关系的相关基本概念和符号理解字典顺序熟练掌握哈塞图的画法，并由此找出极元、最小熟练掌握计算偏序的拓扑排序对应作业,5.6 偏序本节要求,
