离散数学课件 第四章 二元关系-2nd.pdfVIP

第四章 二元关系 大连理工大学软件学院 陈志奎 教授 办公室：综合楼411 ，Tel 实验室：教学楼A318/323 ，Tel 24 Mobile: Email: zkchen@ zkchen00@ 36 回顾 •关系的定义，二元关系 – 笛卡尔积—构成集合（子集） •关系的性质 – 自反，反自反，对称，反对称，传递，不可 传递 •关系相等 •关系压缩与开拓 36 4.3关系的表示 一、关系图 定义：设A 和B为任意的非空有限集，R为任意一个 从A 到B 的二元关系。以A ∪B 中的每个元素为结 点．对每个〈x , y 〉∈R ∧x ∈A ∧y ∈B 皆画一条从x 到y 的有向边，这样得到的一个图称为关系R 的 关系图。 例：A={1,2,4}; B={3,5,6}; 1 3 关系R={1,3,2,6,2,5} 2 5 4 6 A B 36 一、关系图 例：设A={2,3,4,5,6},B={6,7,8,12} ，从A到B 的二元 R {〈x ,y〉|x ∈A ∧y ∈B ∧x整除y} 关系R为 ，画出其 关系图。 解：先求出R R {=〈2，，，，，6〉〈2 8〉〈2 12〉〈，，，，3 6〉〈312〉〈，，，，4 8〉〈4 12〉〈，，，，6 6〉〈6 12〉} 36 一、关系图 xRy xRx xRy ∧yRy xRy ∧yRx xRy ∧yRz ∧zRx 对称关系 反对称关系 36 二、关系矩阵 定义：给定两个有限集合X={x ,x ,…,x }和Y= 1 2 m {y ,y ,…,y }，R是从X 到Y的二元关系，如果有： 1 2 n ⎧1 如果x y ∈R