偏序关系

概念

关系

关系这个概念在我们日常生活中非常常见,比如说他比较高,那只白天鹅很大等等,当我们说类似这些话的时候,我们是在拿一个人或一个事物和另一个人或其他事物相比较,这种比较就是一种关系。

在离散数学及其应用中对关系的描述是:集合的元素之间的关系被表示成一种结构,这种结构叫做关系。它其实是集合间的笛卡尔积的一个子集。我理解根据这个定义,关系就是将集合元素与元素之间建立关联,这个关联通常是按照元素所具有的属性进行关联的。比如:集合A中有两个元素{苹果,橘子},我们怎么给这两个元素建立关系哪?我们可以用这两个元素所包含的营养元素建立关系,比如拿苹果的维生素A含量与橘子的维生素A含量进行比较,拿维生素B进行比较等等。

关系的性质

  1. 自反性

自反性个人理解为元素自己和自己有某个关系。
引用一些离散数学及其应用书中的例子:

  • 正整数集合中所有元素的整除关系都是自反的,比如:5除以5
  1. 反自反性

个人理解为自己和自己没有某个关系。
引用一些离散数学及其应用书中的例子:

  • 整数集合中所有元素的整除关系有反自反的,比如:0除以0
  1. 对称性

个人理解对称关系是对集合中两个元素a,b某种关系的双向连接,比如:如果aRb那么就有bRa,其实就是a<->b。
比如:张三是李四的同事,那么李四也是张三的同事,所以张三R李四的关系具有对称性;张三是李四的队友,那么李四也是张三的队友,所以张三R李四的关系具有对称性。

  1. 反对称性

个人理解反对称性关系是对集合中两个元素a,b具有某种关系,但是只满足a和b具有这个关系,但是b和a不具有这种关系,其实存在a->b,但是不存在b->a。
比如:通常张三就职与一家公司,那么这家公司并不就职于张三,所以他们是反对称关系;张三想要李四的电话号码,但是李四不一定想要张三的电话号码,所以他们是反对称关系。

  1. 传递性

个人理解传递性是比较容易理解的,比如:a>b,b>c,那么a>c(写到这里突然想到了亚里士多德的三段论:所有的人都会死,苏格拉底是人,所以苏格拉底会死。)。这个就像是一个大前提、一个小前提、一个结论,三个内容都有关联。
比如:张三和李四是亲兄弟,李四和王五是亲兄弟,那么张三和王五是亲兄弟,那么张三、李四和王五的关系是传递的。

  1. 反传递性

反传递性就是干掉传递关系,比如:张三和李四是朋友,李四和王五是朋友,但是张三和王五不是朋友,那么张三、李四和王五的关系不反传递的。现在的社交平台经常通过朋友推荐算法来向你推荐新朋友,是因为你和朋友之间的关系存在了反传递性,所以社交平台通过朋友推荐算法来尝试给你们建立朋友关系的传递性。

关系的表示

表示关系通常使用有向图和无向图。图中的点为集合中的元素,图中的边表示元素之间的某种关系。
无向图可以用来表示是否具有各种关系,图中点如果有一条指向自己的边可以表示自反关系。
有向图可以用来表示对称关系。
下面分别是有向图和无向图(图中没有画自反性):
有向图
偏序关系

无向图
偏序关系

偏序关系

重点来了,铺垫了这么多,终于到了偏序关系。
偏序关系是对于集合上的某种关系,这个关系存在自反性、反对称性和传递性这三种性质的话,就是偏序关系。
简单理解为:集合中不是所有的元素都具有这个关系或者理解为集合中至少有两个元素没关系。
比如:一个集合A={张三,李四,王五,麻子,花脸},他们是一个家族的,比如:张三生了李四和王五,李四生了麻子,王五生了花脸;这样一种关系就是偏序关系
自反性:这个需要假设自己和自己是生了的关系
反对称性:张三生了李四,那么李四就不能有生了张三这个关系
传递性:张三生了李四,李四生了麻子

总结

  1. 偏序关系查一些资料是比较难懂,但是从字面的偏字来上来,偏和全相对,偏理解为部分就可以了,就是部分元素之间有关系,部分元素之间没关系;所有元素都有关系就是全序了。

参考

  1. 离散数学及其应用 第六版
  2. * https://en.wikipedia.org/wiki/Finitary_relation
上一篇:架构模式-微内核架构模式


下一篇:渐进符号 big-O、big-Ω、big-Θ