关系和有向图.docVIP

第四章 关系和有向图Relations and Digraphs 4.1乘积集合和划分Product sets and Partions 乘积集合Product sets A(B ={(a,b) | a(A, b(B} | A(B|=|A|(|B| A1(A2(……(An ={ (a1, a2,……an)| ai(Ai,i=1,2,……,n} 定理1.乘积集合对∪，∩满足分配律 A×(B∪C)=A×B∪A×C A×(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 of A A= A1∩A2∩……∩An, Ai(( , Ai∩Aj=(, i=1,2,……,n . Homework P105-106 17,26 4.2关系和有向图Relations and Digraphs 关系R(A(B R称为A到B上的关系, a Relation from A to B. R(A(A R称为A上的关系, a relation on A. (a,b) (R, 也记作 aRb. 例1． IA ={(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= IA∪{(1,2), (1,3), (1,4), (2,4)}, P是A上整除关系。 由关系派生的集合Sets Arising from Relations 定义域Dom(R) domain of R 关系R(A(B Dom(R)={x| (y(B, (x,y) (R} Dom(IA)=A, Dom(Q)=A-{4}, Dom(P)=A。 值域Ran(R) range of R Ran(R)= {y(B|(x(A, (x,y) (R}. Ran(IA)=A, Ran(A)={2,3,4}, Ran(P)={1,2,3,4}。 A1的像集R(A1) ，x的像集R(x) 关系R(A(B, A1(A. R(A1)={y(B| (x( A1, (x,y) (R}, A1的像集，the R-relative set of A1. R(x)={y(B| (x,y) (R}, x的像集。 定理1. 关系R(A(B,A1(A, A2(A, If A1(A2, then R(A1)(R(A2). R(A1∪A2) (R(A1)∪R(A2). R(A1∩A2) ( R(A1)∩R(A2). 定理2. 关系R(A(B, S(A(B. 如果(a(A,R(a)=S(a), 则R=S. 关系矩阵MR The Matrix of a Relation 关系R(A(B, 关系R的矩阵MR=[mij]， 关系图The Digraph of a 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)} 由关系确定矩阵和图 由矩阵确定关系 由图确定关系 Homework P114-115 18,22,24,28 4.3关系和图的路径Paths in Relations and Digraphs 长度为n的路径a path of length n 从a到b有长度为n的路径π： aRx1, x1Rx2,……, xn-1Rb， 记做π：a,x1,x2,……,xn-1,b. Rn 具有长度为n的路径的关系 关联关系 R∞ connectivity relation for R MR2= MR(MR MRn= MR( MR(MR(……( MR MR(= MR( MR2(MR3(…… 可达矩阵MR*= In(MR( MR2(MR3(…… 两条路径的连接 π1：a1,a2,…,an, π2：b1,b2,…,bm, b1=an π1?π2：a1,a2,…,an,b2,…,bm, Homework P120-121 6,8,18,24,25,26 4.4关系的性质Properties of Relations 自反和反自反关系Reflexive and Irreflexive Relations 自反关系Reflexive Relations 关系R(A(A, (a(A,(a,a)(R IA,P是自反关系。 反自反关系 Irreflexive Relations 关系R(A(A, (a(