第四章关系和有向图4.1-4.4

1、第四章 关系和有向图Relations and Digraphs4.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×(BC)=A×BA×CA×(BC)=A×BA×C(BC)×A=B×AC×

2、A(BC)×A=B×AC×A(AB)×(CD)A×CB×D划分Partion or Quotient set of AA= A1A2An, Ai¹Æ , AiAj=Æ, i=1,2,n .Homework P105-106 17,264.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) Î

3、;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´BDom(R)=x| $yÎB, (x,y) ÎRDom(IA)=A, Dom(Q)=A-4, Dom(P)=A。值域Ran(R) range

4、 of RRan(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, (a) If A1

5、ÍA2, then R(A1)ÍR(A2).(b) R(A1A2) ÍR(A1)R(A2).(c) R(A1A2) Í 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。1

6、11423A=1,2,3,4R=(1,1),(1,2),(2,1),(2,2),(2,3),(2,4), (3,4),(4,1)由关系确定矩阵和图由矩阵确定关系由图确定关系Homework P114-115 18,22,24,284.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 RMR2= MRÄMR MRn

7、= MRÄ MRÄMRÄÄ MRMR¥= MRÅ MR2ÅMR3Å可达矩阵MR*= InÅMRÅ MR2ÅMR3Å两条路径的连接1：a1,a2,an,2：b1,b2,bm,b1=an12：a1,a2,an,b2,bm,Homework P120-1216,8,18,24,25,264.4关系的性质Properties of Relations自反和反自反关系Reflexive and Irreflexive Relations自反关系Reflexive Relations关系

8、RÍA´A, "aÎA,(a,a)ÎRIA,P是自反关系。反自反关系 Irreflexive Relations关系RÍA´A, "aÎA,(a,a)ÏRQ是反自反关系。对称Symmetric，不对称 asymmetric，反对称antisymmetric Relations关系对称Symmetric，(a,b)RÞ(b,a)R不对称 asymmetric，(a,b)RÞ(b,a)ÏR反对称antisymmetric (a,b)R (b,a)R Þ a=b

9、传递 Transitive (a,b)R (b,c)R Þ (a,c)R.大于等于，小于等于，恒等，整除关系都是传递关系。定理1.关系R是传递的当且仅当RnÍR, 即如果a,b有长度大于1的边则有长度为1的边。定理2. R是A上关系,则(a) R自反 则"aÎA, aR(a).(b) R对称 则 aR(b) iff bR(a)(c) R传递 则 bR(a), cR(b) Þ cR(a).偏序关系Partial Order1.自反 Reflexive "aÎA, (a,a)ÎR2反对称antisymmetric(a,b)R (b,a)R Þ a=b3传递Transitive(a,b)R (b,c)R Þ (a,c)R.大于等于，小于等于，恒等，整除关系都是偏序关系。（A, Í）集合对于Í是偏序。树是偏序。全序关系，线性序关系linear order偏序1.2.3.4 "a,bÎA,(a,b)ÎR(b,a)R.大于等于，小于等于是全序，整除，（A, Í）不是。严格序strict or