二元关系 4.5 偏序关系.ppt

1 离散数学DiscreteMathematics 主讲 陈哲云青岛理工大学计算机工程学院2013 09 第4章二元关系 二元关系 4 1二元关系基本概念 重点 4 2关系的运算4 3关系的性质 重点 4 4关系的闭包4 5等价关系和偏序关系 重点及难点 4 6函数的基本概念 偏序关系 偏序关系Hasse图 重点 重要元素 重点 拓扑排序 偏序关系 定义偏序关系 设A上的二元关系R 如果R是自反的 反对称的 传递的 则称R为偏序关系 记为 称为偏序集 若 R 称 x小于等于y 记作x y 偏序关系 例1几个常见的偏序关系 1 A上的小于等于关系 A 1 2 3 4 5 6 1 x y x y A 2 A上的整除关系 A 1 2 3 4 5 6 2 x y x y A 3 P A 上的包含关系 A 1 2 3 3 s1 s2 s1 s2 P A 4 任务集S T1 T2 Tn 上的关系R4 Ti Tj或Ti必须在Tj之前完成 偏序关系 关于例1 4 的一个举例 如完成室内闪光拍照的任务 任务集T包括任务 1 打开镜头盖 2 照相机调焦 3 打开闪光灯 4 按下快门按钮 在T上定义关系R R 如果i j或者任务i必须在任务j之前完成 则R 偏序关系 定义设R为非空集合A上的偏序关系 x y A 则x与y可比 x y y x定义设R为非空集合A上的偏序关系 x y A 则y盖住x x y且不存在z A使得x z y Hasse 哈斯 图 例2设A 2 3 6 12 24 36 是A上的整除关系R 画出其关系图 关系图 2 3 6 12 36 24 2 3 6 12 36 24 简化的关系图 Hasse图 Hasse图 简化的关系图 Hasse图 哈斯图 1 自反性 每个顶点都有自回路 省去 2 反对称性 两个顶点间只可能有一个箭头 从小到大 或从低到高 安置顶点 可省略箭头 3 传递性 由于有 R 则 R 故只画 对应的边 省略边 Hasse图 Hasse图的画法 层次 与 连线 1 极小元放在第一层 最底层 2 若第n层已放好 则第n 1层的元素满足至少能盖住第n层的一个元素 层次 3 若y盖住x 则x y之间连线 连线 注 哈斯图体现了偏序集中元素间的 大小 和 层次 关系 Hasse图 例3画出例1中各关系的Hasse图 A 1 2 3 4 5 6 7 8 9 B a b c S 1 2 3 4 1 x y x y A 2 x y x y A 3 s1 s2 s1 s2 P B R4 Ti Tj或Ti必须在Tj之前完成且Ti Tj S Hasse图 1 2 全序集 Hasse图 4 3 3 4 全序关系 定义全序关系 任意两个元素都可比设是一个偏序集 若对任意x y A 总有x y或y x 二者必居其一 则称 为全序关系 或者线序关系 称为全序集 或者线序集 或者链 偏序集中的重要元素 设偏序集 B A b表示相应的特殊元素 B的极小元 B中没有比b小的元素b B且 x x B x b B的最小元 B中所有的元素都比b大b B且 x x B b x 极大元和最大元类似定义 注 上述元素都在B中寻找 偏序集中的重要元素 设偏序集 B A b表示相应的特殊元素 B的上界 B中所有的元素都比b小b A且 x x B x b B的上确界上确界 B的上界的最小元下界和下确界类似定义 注 上述元素都在A中寻找 偏序集中的重要元素 例4设偏序集 求A的极小元 极大元 最小元 最大元 设B b c d 求B的下界 上界 下确界 上确界 解 极小元 a b c g 极大元 a f h 没有最小元与最大元 B的下界和下确界都不存在 上界有d和f 上确界为d 偏序集中的重要元素 性质 1 对于有穷集 极小元和极大元一定存在 可能存在多个 2 最小元和最大元不一定存在 如果存在一定惟一 3 最小元一定是极小元 最大元一定是极大元 4 孤立结点既是极小元 也是极大元 5 下界 上界 下确界 上确界不一定存在 存在不一定唯一 6 下确界 上确界如果存在 则惟一 偏序集中的重要元素 练习的Hasse图如下所示 讨论当B取相应集合时 其最大元 最小元 极大元 极小元 上界 下界 上确界 下确界 B1 a b B2 a b c B3 a b c d B4 b c d f B5 a c f i 无 小结 偏序关系是 次序 关系 但不一定是 全序 关系 哈斯图是偏序集的简化图 通过 层次 关系来表达元素的 大小 关系 偏序集中的特殊元素可以通过哈斯图来寻找 作业 1 下图中给出了偏序集的Hasse图 1 试分别以集合 关系矩阵 关系图三种方式写出该偏序关系 2 求A的最大 最小元 若存在的话 3 求A的极大 极小元 4 求子集 b c d c d e 和 a b c 的上下界以及上下确界 作业 2 设S 0 1 F是S中的字符构