04-关系和有向图-离散数学讲义-海南大学(共十一讲).doc

4. 关系和有向图 Relations and Digraphs 乘积集合和划分 Product sets and Partions 乘积集合 Product sets A ?B ={(a,b) |a ? A,b ? B} |A ? B|=|A| ?|B| A 1?A 2?……?A n ={ (a 1,a 2, …… a n )|a i?A i ,i=1,2, ……,n} 定理 1. 乘积集合对∪,∩满足分配律 A× (B∪ C)=A ×B∪A×CA× (B∩ C)=A ×B∩A×C (B∪ C)× A=B ×A∪C×A (B∩ C)× A=B ×A∩C×A (A∪ B)× (C∪ D)≠A×C∪B×D 划分 Partion or Quotient set ofA A=A 1∩A 2 ∩……∩ A n,A i??,A i∩A j= ?, i=1,2, ……,n. 关系和有向图 Relations and Digraphs 关系 R?A?BR 称为 A到B 上的关系,a Relation from A to B. R?A?AR 称为 A 上的关系,a relation on A. (a,b) ? R, 也记作 aRb. A ={(a,a)| a? A} 等于关系。例2. A={1,2,3,4}, Q={(1,2), (1,3),(1,4),(2,3),(2,4),(3,4)} Q是A 上小于关系。例3. P=I A∪{(1,2), (1,3), (1,4), (2,4)}, P是A 上整除关系。由关系派生的集合 Sets Arising from Relations 定义域 Dom(R) domain ofR 关系 R?A?B Dom(R)={x| ?y? B, (x,y) ? R} Dom(I A )=A, Dom(Q)=A -{4} , Dom(P)=A 。值域 Ran(R) range ofR Ran(R)= {y ? B| ?x ? A, (x,y) ? R}. Ran(I A )=A, Ran(A)={2,3,4}, Ran(P)={1,2,3,4} 。 A 1 的像集 R(A 1),x 的像集 R(x) 关系 R?A? B,A 1? A. R(A 1 )={y ? B|?x?A 1, (x,y) ? R}, A 1 的像集, the R-relative set ofA 1. R(x)={y ? B| (x,y) ? R}, x 的像集。定理 1. 关系 R ?A ? B,A 1? A,A 2? A, (a) IfA 1?A 2, then R(A 1) ? R(A 2 ). (b) R(A 1∪A 2) ? R(A 1)∪ R(A 2 ). (c) R(A 1∩A 2) ? R(A 1)∩ R(A 2 ). 定理 2. 关系 R ?A ? B,S ?A ? B. 如果?a ? A,R(a)=S(a), 则 R=S. 关系矩阵 M R The Matrix ofa Relation 关系 R ?A ? B, 关系 R 的矩阵 M R =[m ij],????0 1 ijmRba Rba ji ji??),( ),( ???????????????1000 0100 0010 0001 AIM???????????????0000 1000 1100 1110 QM???????????????1000 0100 1010 1111 pM 关系图 The Digraph ofa Relation 关系 R?A? A, G=(V,E), 定点集合 V=A, 边集合 E=R 。 A={1,2,3,4} R={(1,1),(1,2),(2,1), (2,2),(2,3),(2,4), (3,4),(4,1)} ?????????????0001 1000 1111 0011 RM 由关系确定矩阵和图由矩阵确定关系由图确定关系 Homework P114-115 18,22,24,28 关系和图的路径 Paths in Relations and Digraphs 长度为 n 的路径 a path of length n 从a到b 有长度为 n 的路径π: 14 23 aRx 1,x 1 Rx 2, ……,x n-1 Rb, 记做π: a,x 1,x 2, ……,x n-1, n 具有长度为 n 的路径的关系关联关系 R ∞ connectivity relation for R M R 2=M R?M RM R n=M R?M R?M R?……?M RM R?=M R?M R 2?M R 3?……可达矩阵 M R *=I n?M R?M R 2?M R 3?……两条路径的连接π 1:a