离散数学_九章:关系(3)(一)

简介: 离散数学_九章:关系(3)(一)

1、用集合表示关系


关系是序偶的集合,所以描述集合能用的方法一般都可以描述关系,比如枚举满足关系的所有序偶,比如叙述满足关系的性质。


前面的例子都是用集合表示关系,这里不赘述


2、用矩阵表示关系


矩阵表示关系

有限集之间的关系可用0-1 矩阵表示:


假设 R 是从 A = { a1, a2,…,am } 到 B = { b1, b2,…,bn } 的关系,则A×B上的所有关系可以用一个 m×n的长方形 0-1 矩阵 来表示。


关系R由矩阵 MR = [ mij ] 表示,其中

当 ai 与 bj 相关时,表示 R 的 0-1 矩阵的 (i, j) 项是1,如果ai 与 bj 无关系,则是0


📘例1:

假设 A = { 1, 2, 3 },B = { 1, 2 }。令 R 为 A 到 B 的关系,如果 a∈A,b∈B 且 a > b,则 R 包含 (a, b)。表示 R 的矩阵是什么(假设元素的顺序与递增的数值顺序相同)?


由题意得,R = { (2, 1), (3, 1), (3, 2) },因此矩阵为:


📘例2:

设 A = { a1, a2, a3 },B = { b1, b2, b3, b4, b5 }。哪些有序对在下面的矩阵所表示的关系 R 中?


因为 R 是由 mij = 1 的有序对 (ai, bj) 构成的,所以

R = { (a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5) }


⭐集合上的关系矩阵

表示定义在一个集合上的关系的矩阵是一个方阵,可以用这个矩阵确定关系是否有某种性质


R 自反时

R 是自反的,当且仅当 MR 的主对角线上的所有元素都等于1

❗ 注意:非主对角线上的元素可以是 0 或 1



R 对称时

R 是对称关系,当且仅当 若mij = 1 则 mji = 1


换句话说:R 是对称关系,当且仅当 MR = (MR)T


(沿主对角线对称)


R 反对称时

R 是反对称关系,当且仅当 i ≠ j 时,mij = 0 或 mji = 0(至少有一个得是0)

📘例:

假设集合上关系 R 由下图矩阵表示,R 是自反的、对称的和反对称的吗?

判断自反:因为这个矩阵中所有的对角线元素都等于1,所以 R 是自反的。

判断对称:由于 MR 是对称的,所以 R 是对称的。

判断反对称:因为 m1,2 和 m2,1 都是1,所以 R 不是反对称的


⭐确定关系合成的矩阵

确定关系合成的矩阵:已知两个关系的关系矩阵,求这两个关系矩阵的合成矩阵

本质是关系矩阵的布尔积,理解上可以直接把两个矩阵相乘(注意顺序,A×B和B×A不一样),0仍是0,大于等于1的写成1

相关文章
|
5月前
|
机器学习/深度学习 算法 Java
数论中的十个基本概念
数论中的十个基本概念
|
算法 Android开发 Python
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
59 0
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
|
11月前
|
算法
代码随想录算法训练营第四十一天 | LeetCode 416. 分割等和子集
代码随想录算法训练营第四十一天 | LeetCode 416. 分割等和子集
44 1
代码随想录算法训练营第四十一天 | LeetCode 416. 分割等和子集
|
11月前
|
算法
代码随想录算法训练营第二十四天 | LeetCode 77.组合
代码随想录算法训练营第二十四天 | LeetCode 77.组合
87 0
|
机器学习/深度学习 数据库
离散数学_九章:关系(2)
离散数学_九章:关系(2)
103 1
|
Python
离散数学_九章:关系(6)(一)
离散数学_九章:关系(6)(一)
103 0
|
机器学习/深度学习 移动开发
离散数学_九章:关系(4)(二)
离散数学_九章:关系(4)(二)
141 0
离散数学_九章:关系(3)(二)
离散数学_九章:关系(3)(二)
78 0
|
数据可视化
离散数学_九章:关系(6)(二)
离散数学_九章:关系(6)(二)
323 0
离散数学_九章:关系(4)(一)
离散数学_九章:关系(4)(一)
91 0