第四章关系和有向图10月23日周四讲稿.doc

第四章 关系和有向图Relations and Digraphs4.4关系的性质Properties of Relations自反和反自反关系Reflexive and Irreflexive Relations自反关系Reflexive Relations关系RAA, aA,(a,a)RIA,P是自反关系。反自反关系 Irreflexive Relations关系RAA, aA,(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传递 Transitive (a,b)R (b,c)R (a,c)R.大于等于，小于等于，恒等，整除关系都是传递关系。定理1.关系R是传递的当且仅当RnR, 即如果a,b有长度大于1的边则有长度为1的边。定理2. R是A上关系,则(a) R自反 则aA, aR(a).(b) R对称 则 aR(b) iff bR(a)(c) R传递 则 bR(a), cR(b) cR(a).偏序关系Partial Order1.自反 Reflexive aA, (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,bA,(a,b)R(b,a)R.大于等于，小于等于是全序，整除，（A, ）不是。严格序strict order1.反自反 irreflexive2.传递 transitive严格线性序strict linear order严格序4 a,bA,(a,b)Ra=b(b,a)R.大于，小于都是严格线性序。Homework P127-12810,12,14,20,26,30,324.5等价关系 Equivalence Relations等价关系R是A上关系，满足：1自反2对称3传递恒等IA是等价关系 三角形全等，三角形相似是等价关系集合基数相等是等价关系Z上同余关系是等价关系nZ+, a,bZ, ab(n) iff n|(a-b), 或 a%n=b%n 等价关系与划分定理1.设P是集合A的一个划分，定义A上关系R:a R b 当且仅当a,b属于P的同一分块则R是等价关系。引理1 设R是A上等价关系，则a R b当且仅当 R(a)=R(b)证明 设R(a)=R(b)，则bR(a), 因此a R b反之cA, 设cR(a)，则 a R c,由对称性，c R a. 由a R b，传递性有c R b. 因此cR(b).于是 R(a)R(b). 同理有R(b)R(a). 从而R(a)R(b)。引理2 设R是A上等价关系，则R(a)R(b)当且仅当 R(a)=R(b)证明存在cR(a)R(b)，aRc,cRb.由传递性aRb, 由引理1 R(a)=R(b)。定理2设R是A上等价关系，PR(x)|xA，则P是A的一个划分。且划分P确定的等价关系是R.证明.aA, aR(a)，A=P=R(a),由引理1，2，R(a)R(b)= 或R(a)R(b)。因此P是A的一个划分。a,b属于P的同一分块，a,bR(x),则aRb. P确定的等价关系就是R.称R(a)为a的等价类。也用a表示。划分P也记作A/R，Z关于n的同余关系的划分记作Zn=Z/(n)=0,1,，n-1=0,1,2,，n-1.a+b=a+b,ab=ab.Homework p132-13312,20,16,244.6关系和图的计算机表示Computer Representation of Relations and Digraphs4.7关系的运算Operations on Relations设R和S都是A到B的关系，R,SAB.RS, RS，都是A到B的关系。1.关系的交 (a,b)RS iff (a,b)R且(a,b)S2. 关系的并(a,b)RS iff (a,b)R或(a,b)S3关系的补complementary relation =AB-R,(a,b) iff (a,b)R.2关系的逆inverse relationR-1AB,(a,b)R-1iff (b,a)R.(R-1)-1=RDom(R-1)=Ran(R),Ran(R-1)=Dom(R)., -1 = . = .得到 ? . ?关系运算相应的图 矩阵定理1设R和S都是A到B的关系，R,SAB.(a) R S R-1 S-1(b) R S (c) (RS)-1= R-1S-1 (RS)-1= R-1S-1(d) 定理2.设R和S都是A上关系，R,SAA. (a) R自反R-1自反。 (b) R和S自反 RS,RS自反。(c) R自反 反自反。定理3设R是A上关系，RAA.(a) R对称 R=R-1(b) R反对称 RR-1IA.(c) R不对称 RR-1.定理4设R和S都是A上关系，R,SAA.(a) R对称 R-1,对称。(b) R,S对称RS,RS对称。定理5设R和S都是A上关系，R,SAA. (a)(RS)2R2S2.(b) R,S传递RS传递。(c) R,S是等价关系RS是等价关系。A/(RS)是A/R，A/S两个划分的交。闭包closure设R是A上关系，RAA.R的自反闭包r(R)，是A上最小的一个关系R1,R R1, R1自反。R的对称闭包s(R)，是A上最小的一个关系R1,R R1, R1对称。R的传递闭包tr(R)，是A上最小的一个关系R1,RR1, R1传递。r(R)=RIA, s(R)=RR-1,tr(R)=R.关系的复合composition设R是集合A到B的关系，S是集合B到C的关系。R和S的复合，记做SR,是A到C上的关系：(a c)SR: 存在bB,(a,b)R, (b,c)S.a(SR)c: $bB, a R b, b S c定理6.设R是集合A到B的关系，S是集合B到C的关系,