第工科离散数学课件 四章 4_2_关系运算(3) - 关系运算的图和矩阵实现.pptx

知识回顾4.2 关系运算-关系运算的图和矩阵实现关系（二元）关系：序偶的集合。 ——x, y?R = x R y = x与y有关系R X到Y的关系：X?Y的子集。X上的关系（X到X的关系）：X?X的子集。 ——2|X|2种关系2. 特殊关系 ——?、U恒等关系IX： X的所有元素与自身组成的序偶x, x的集合： IX = {x, x?x?X}整除关系：若干整数组成的集合A上的整除关系：?= {x, y?x, y ? A? x整除y }模m同余关系：?上的模m同余关系：H = {x, y?x, y?? ? (y-x)/m是整数} = {x, y?x, y?? ? x ≡ y (mod m)} 4.2 关系运算-关系运算的图和矩阵实现3. 关系运算关系的逆：设R是X到Y的二元关系，将其每个序偶的元素交换顺序所得到的关系称为R的逆关系，记作 R-1 或RC：R-1 = {y, x?x, y?R}关系的复合（合成）：设R和S分别是X到Y和Y到Z的关系，连接R和S的序偶所得到的关系：R°S = {x, z?x∈X ? z∈Z ??y(y∈Y?x, y∈R?y, z∈S)} 关系运算的性质： (R°S)°T = R° (S°T )，(R°S)-1 = S-1° R-1， R°IA = IA°R = R 4.2.3 关系运算的图和矩阵实现4.2 关系运算-关系运算的图和矩阵实现1. 由关系图实现关系运算求逆关系：将原关系图的所有连线箭头方向取反。求复合关系：将所有 “首尾相连”的两条连线合成一条连线。例4-9：设X = {1, 2, 3, 4}，Y = {2, 3, 4}，Z = {1, 2, 3}，求S°T，并绘制出 S°T 的关系图： S = {x, y?x∈X?y∈Y? x+y = 6}，T = {y, z?y∈Y?z∈Z?y – z = 1}解： S°T = {2,3,3,2,4,1} = {x, z | x∈X?z∈Z ? x+z = 5}。12342341231234123S：X到Y ，T：Y到Z S°T：X到Z 2. 由关系矩阵实现关系运算4.2 关系运算-关系矩阵运算求R的逆关系： 将关系R的关系矩阵是MR转置。求R、S的复合关系：若关系R、S分别是X到Y、Y到Z的关系，|X| = m，|Y| = n，|Z| = p，记R、S和R°S 的关系矩阵分别为MR=[rij]m×n， MS=[sij]n×p 和MR°S = [cij]m×p，则 cij = ?nk =1 rik?skj , 1≤i ≤m, 1≤ j ≤p——可以用逻辑乘法、加法代替普通乘法、加法xm-1xmx1x2?xi是否可通过某个yk连上？?yn-1yny1y2?yk?zp-1zpz1z2?zj?——复合关系矩阵恰好是两个关系矩阵的积： MR°S = MR×MS= ×cijri1 rins1j snj矩阵乘法 例4-8：已知集合A = {1, 2, 3, 4}上的关系 R = {1, 2, 3, 4, 3, 2, 2, 2}，S = {4, 2, 2, 3, 3, 1, 1, 3}利用关系矩阵求R°S 。4.2 关系运算-关系运算的性质解： MR = , MS =0 1 0 00 1 0 00 1 0 10 0 0 00 0 1 00 0 1 01 0 0 00 1 0 0有 MR°S =0 0 1 00 0 1 00 1 1 00 0 0 0故 R°S = {1, 3, 2, 3, 3, 2, 3, 3}。