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

第四章关系和有向图RelationsandDigraphs4.4关系的性质PropertiesofRelations自反和反自反关系ReflexiveandIrreflexiveRelations自反关系ReflexiveRelations关系RAA,aA,(a,a)RIA,P是自反关系。反自反关系IrreflexiveRelations关系RAA,aA,(a,a)RQ是反自反关系。对称Symmetric，不对称asymmetric，反对称antisymmetricRelations关系对称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是传递的当且仅当RnR,即如果a,b有长度大于1的边则有长度为1的边。定理2.R是A上关系,则(a)R自反则aA,a∈R(a).(b)R对称则a∈R(b)iffb∈R(a)(c)R传递则b∈R(a),c∈R(b)c∈R(a).偏序关系PartialOrder1.自反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,）集合对于是偏序。树是偏序。全序关系，线性序关系linearorder偏序1.2.3.＋4．a,bA,(a,b)R∨(b,a)∈R.大于等于，小于等于是全序，整除，（A,）不是。严格序strictorder1.反自反irreflexive2.传递transitive严格线性序strictlinearorder严格序＋4’．a,bA,(a,b)R∨a=b∨(b,a)∈R.大于，小于都是严格线性序。HomeworkP127-12810,12,14,20,26,30,324.5等价关系EquivalenceRelations等价关系R是A上关系，满足：1．自反2．对称3．传递恒等IA是等价关系三角形全等，三角形相似是等价关系集合基数相等是等价关系Z上同余关系是等价关系n∈Z+,a,b∈Z,a≡b(n)iffn|(a-b),或a%n=b%n等价关系与划分定理1.设P是集合A的一个划分，定义A上关系R:aRb当且仅当a,b属于P的同一分块则R是等价关系。引理1设R是A上等价关系，则aRb当且仅当R(a)=R(b)证明设R(a)=R(b)，则b∈R(a),因此aRb反之cA,设c∈R(a)，则aRc,由对称性，cRa.由aRb，传递性有cRb.因此c∈R(b).于是R(a)R(b).同理有R(b)R(a).从而R(a)＝R(b)。引理2设R是A上等价关系，则R(a)∩R(b)≠当且仅当R(a)=R(b)证明存在c∈R(a)∩R(b)，aRc,cRb.由传递性aRb,由引理1R(a)=R(b)。定理2设R是A上等价关系，P＝{R(x)|x∈A}，则P是A的一个划分。且划分P确定的等价关系是R.证明.aA,a∈R(a)，A=∪P=AaR(a),由引理1，2，R(a)∩R(b)=或R(a)＝R(b)。因此P是A的一个划分。a,b属于P的同一分块，a,b∈R(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],[a]×[b]=[a×b].Homeworkp132-13312,20,16,244.6关系和图的计算机表示ComputerRepresentationofRelationsandDigraphs4.7关系的运算OperationsonRelations设R和S都是A到B的关系，R,SA×B.R∩S,R∪S，R都是A到B的关系。1.关系的交(a,b)∈R∩Siff(a,b)∈R且(a,b)∈S2.关系的并(a,b)∈R∪Siff(a,b)∈R或(a,b)∈S3．关系的补complementaryrelationR=A×B-R,(a,b)∈Riff(a,b)R.2关系的逆inverserelationR-1A×B,(a,b)∈R-1iff(b,a)∈R.(R-1)-1=RDom(R-1)=Ran(R),Ran(R-1)=Dom(R).-1=,-1=.=.∩得到?.∪?关系运算相应的图矩阵定理1设R和S都是A到B的关系，R,SA×B.(a)RSR-1S-1(b)RSSR(c)(R∩S)-1=R-1∩S-1(R∪S)-1=R-1∪S-1(d)SRSRSRSR定理2.设R和S都是A上关系，R,SA×A.(a)R自反R-1自反。(b)R和S自反R∩S,R∪S自反。(c)R自反R反自反。定理3设R是A上关系，RA×A.(a)R对称R=R-1(b)R反对称R∩R-1IA.(c)R不对称R∩R-1.定理4设R和S都是A上关系，R,SA×A.(a)R对称R-1,R对称。(b)R,S对称R∩S,R∪S对称。定理5设R和S都是A上关系，R,SA×A.(a)(R∩S)2R2∩S2.(b)R,S传递R∩S传递。(c)R,S是等价关系R∩S是等价关系。A/(R∩S)是A/R，A/S两个划分的交。闭包closure设R是A上关系，RA×A.R的自反闭包r(R)，是A上最小的一个关系R1,RR1,R1自反。R的对称闭包s(R)，是A上最小的一个关系R1,RR1,R1对称。R的传递闭包tr(R)，是A上最小的一个关系R1,RR1,R1传递。r(R)=R∪IA,s(R)=R∪R-1,tr(R)=R.关系的复合composition设R是集合A到B的关系，S是集合B到C的关系。R和S的复合，记做S◦R,是A到C上的关系：(ac)∈S◦R:存在b∈B,(a,b)∈R,(b,c)∈S.a(S◦R)c:b∈B,aRb,bSc定理6.设R是集合A到B的关系，S是集合B到C的关系,A1A。(S◦R)(A1)=S(R(A1)).MS◦R=MRMS.定理7.设R是集合A到B的关系，S是集合B到C的关系,T是集合C到D的关系,则T◦(S◦R)=(T◦S)◦R.定理8(S◦R)－1＝R-1◦S-1HomeworkP148-1506,8,10,14,16,24,26,28