离散
序关系
偏序关系
标准定义请看书上P140页
以下全是自己理解
定义及举例
设 A 是一个非空集,P 是 A 上的一个关系,若关系P是自反的、反对称的、和传递的,则称P是集合A上的偏序关系。
即P适合下列条件:
- 对任意的a∈A,(a,a)∈P
- 若(a,b)∈P且(b,a)∈P,则a=b
- 若(a,b)∈P,(b,c)∈P,则(a,c)∈P
则称 P 是 A 上的一个偏序关系。
带偏序关系的集合 A 称为偏序集或半序集。
若P是A上的一个偏序关系,我们用a≤b来表示(a,b)∈P。
举如下例子说明偏序关系:
- 1.实数集上的小于等于关系是一个偏序关系
- 2.设 S 是集合,P(S)是 S 的所有子集构成的集合,定义 P(S)中两个元素 A≤B 当且仅当 A 是 B 的子集,即 A 包含于 B,则P(S)在这个关系下成为偏序集。
- 3、设 N 是正整数集,定义 m ≤ n 当且仅当m能整除n,不难验证这是一个偏序关系。注意它不同于N上的自然序关系。
偏序是在集合 P 上的二元关系(≤),它是自反的、反对称的、和传递的,就是说,对于所有 P 中的 a, b 和 c,有着:
- a ≤ a (自反性)
- 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
- 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
关系图的特点
- 每个结点都有自回路
- 每对结点之间若有定向弧线, 一定不是成对出现的
- 若两个结点之间有路,则一定有一条长度为1的路
关系矩阵的特点
- 对角线元素均为1
- 关于对角线对称的两个元素不能同时为1
偏序关系的哈斯图
定义
根据盖住的概念给出了偏序关系图的一种画法, 这种画法画出的图称为哈斯图,作图规则如下:
- 用小圆圈代表元素
- 若元素a≠b且a≤b时,则结点a画 在结点b的下方
- 若b盖住a,则在a与b之间用直线连接。由于所有边的箭头向上,故省去箭头
补充知识
最大元和最小元
设< A,⩽>
是偏序集,B 是 A 的任何一个子集, 若存在元素 b∈B, 使得
对任意 x∈B, 都有x⩽b, 则称 b 为 B 的最大元;
对任意 x∈B, 都有b⩽x, 则称 b 为 B 的最小元
极大元和极小元
设 < A,⩽>
是偏序集,B 是 A 的任何一个子集, 若存在元素 b∈B, 使得
对任意 x∈B, 满足b⩽x⇒x = b, 则称 b 为 B 的极大元
对任意 x∈B, 满足x⩽b⇒x = b, 则称 b 为 B 的极小元
具体举例如下
哈斯图的画法要确定层数。也就是谁在上,谁在下。结合书上的一些定义进行总结:(恒等关系在哈斯图上体现不出来就不说了。)
1.先把没有出现在值域(<a,b>, 其中b为值域)的元素放在第一排。如有多个,一起放在第一排。比如在关系集合中,{<1,2> <1,3> <1,4> <1,5> <1,6> <2,4> <2,6> ❤️,6>},我们发现只有1没有出现在值域中,所以就放在第一排。
2.再把在第一排元素所在的关系全部扔了。出现在值域的元素(扔掉的关系且不会出现在未扔掉关系里)和只出现在前域的元素(未扔掉的关系)放在第二排。此时扔掉的元素为{<1,2> <1,3> <1,4> <1,5> <1,6>},未扔掉的元素为{ <2,4> <2,6> ❤️,6>}。扔掉的关系的值域为{2,3,4,5,6}, 未扔掉的关系的全部元素为{2,3,4,6}, 5出现在集合{2,3,4,5,6}中,而未出现在{2,3,4,6},所以5放到第二排,所以5放到第二排。未扔掉的关系集合前域为2,3,只出现在前域的元素为2,3,所以这两个元素也放在第二排。
3.以此类推,直到元素全部有了自己的位置。
4.在两层数之间,只有上层盖住下层时才能相连。
为什么是这样?我们只有这样,才保证了这一层和上一层(下一层)有盖住关系。什么是盖住?比如在例题中关系的集合中的<1, 4>就不是盖住关系,因为存在<1, 2>,<2, 4>,盖住就是关系<a, b>,且<a, b>中不存在c,使得<a, c>, <c, b>。这里我举个我们学校自编教材书上的一个例子。题目是这样的:已知集合A={1,2,3,4,5,6},B={2,3,5},R是A上的整除关系,求R的哈斯图,并求B得最大元,最小元,极大元,极小元,上界,上确界,下届,下确界。利用刚刚总结的那几句话来画哈斯图。先写出我们关系的集合{<1,2> <1,3> <1,4> <1,5> <1,6> <2,4> <2,6> ❤️,6>}。这里不写恒等关系,在画哈斯图时用不到。
1.第一层:1;
2.第二层:2,5,3;
3.第三层:4,6;
确定盖住关系后,我们来画出哈斯图
OK,哈斯图画好了,我们要利用哈斯图去寻找极大元之类的了。我根据书上的定义做出如下总结:
最大元素就是在子集中(例题中指B={2,3,5})处于最高层且每个元素通过图中路径都可以找到它且它的上面没有元素。
最小元素就是在子集中处于最低层且每个元素通过图中路径都可以找到它且它的下面没有元素。
极大元素就是在子集中它的上面没有元素。
极小元素就是在子集中它的下面没有元素。
(记住:这里如果是子集,应当将子集当成一个单独的整体,而不受全集的影响。)
上届:所有子集内的元素沿着路径向上都可以找到的元素(这里包括子集和子集以外的元素)。根据上面所说的话,我们可以断定上届也可以是子集内的元素。
下届:所有子集内的元素沿着路径向下都可以找到的元素(这里包括子集和子集以外的元素)。根据上面所说的话,我们可以断定下届也可以是子集内的元素。
上确界:这里我们可以将上届元素看成一个独立的整体,而上确界就是这个集合的最小元,我们称为最小上届。。根据上面所说的话,我们可以断定上届也可以是上确界。
下确界:这里我们可以将下届元素看成一个独立的整体,而下确界就是这个集合的最大元,我们称为最大下届。根据上面所说的话,我们可以断定下届也可以是下确界。
我们还拿上面的例子为例:先将子集看为一个整体,再找极大元,极小元,最大元,最小元。
我们发现:2,3,5上面和下面都没有元素,所以2,3,5是极大元,极小元。但是我们发现2,3,5之间压根没线,所以就没有最大元和最小元之说。2,3,5沿向上路径找不到一个元素,所以也没有上确界和上届。2,3,5向下找可以找到一个元素1,所以元素1为下界。下届元素也可以为下确界,自回路嘛,1自己找到自己,所以1也为下确界。
最后的补充
盖住关系
如果 x ≼ y 且不存在 z ∈ A 使得 x ≼ z ≼ y, 则称 y 覆盖 x.
链和反链
设<A,≼>是一个偏序集合
在A的一个子集中,如果每两个元素都是有关系的,则称这个子集为链。
在A的一个子集中,如果每两个元素都是无关的,则称这个子集为反链。
我们约定,若A的子集只有单个元素,则这个子集既是链又是反链。