第工科离散数学课件 四章 4_6_序关系(3) - 链与全序关系.pptx

4.6 偏序关系-链与全序关系4.6.3 链与全序关系1．由可比元素组成链[链] 设<A, ? >是一个偏序集，C ? A，C ? ? 。若C中任意两个元素都有关系，即二者是可比的，则称C为链。示例： A为单位员工集合， ?表示上下级关系。则C = {总经理，部门经理，职工甲}是链，而D = {职工甲，职工乙，职工丙}是反链。非链 ? 反链；非反链 ? 链。[反链]若C中任意两个元素都没有关系，即二者不可比，称C为反链。——约定：只含有一个元素的子集既是链也是反链。 4.6 偏序关系-链与全序关系问：哈斯图中，如何找到链和反链？答：从任何一元素开始，由下到上“走过的路”是一个链。没有两个元素处于同一条路上的子集是一个反链。2．全序关系[全序(线序)] 设<A, ? >是一个偏序集。若A本身是一个链，则称<A, ? >为全序集，称?为全序关系或线序关系。——全序就是指全都有序，其哈斯图是“一个链”或“一条线”，任意两元素都是可比的示例：整数集?上的≤关系、集合 {?, {a}, {a, b}, {a, b, c}}上的?关系都是全序关系。1246231 4.6 偏序关系-链与全序关系例4-31：找出集合{0, 1, 2, 3}上包含序偶<0, 3>和<2, 1>的线序关系。解：只要求满足0 ? 3和2 ? 1，故有6种可能的线序关系。102332011032321030121230