二元关系课件.pptVIP

從簡化圖找最大相容類：------找最大完全多邊形。最大完全多邊形：含有結點最多的多邊形中，每個結點都與其它結點相聯結。一個孤立頂點--------完全0邊形；兩個結點間有連線(非三角形中的一邊)---完全1邊形；三角形------完全3邊形；完全4邊形，…如下圖所示：在相容關係簡化圖中，每個最大完全多邊形的結點集合構成一個最大相容類。上例中最大相容類{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}分別對應最大完全四、三、一、零邊形。。。。x1。。。。。。。i=1(i---列,j---行)A[4,1]=11行+4行→4行i=2A[1,2]=1,1行+2行→1行A[2,2]=1,2行+2行→2行A不變A[4,2]=1,4行+2行→4行,4行全1,A不變i=3A[1,3]=1,1行+3行→1行,3行全0,A不變A[2,3]=1,2行+3行→2行,3行全0,A不變A[4,3]=1,4行+3行→4行,3行全0,A不變i=4A[1,4]=1,1行+4行→1行A[4,4]=1,4行+4行→4行A不變,最後A=Mt(R)A=MR=A=A的初值:A=A=四.性質定理5.R是A上關係，則⑴R是自反的，當且僅當r(R)=R.⑵R是對稱的，當且僅當s(R)=R.⑶R是傳遞的，當且僅當t(R)=R.證明略，因為由閉包定義即可得。定理6.R是A上關係，則⑴R是自反的，則s(R)和t(R)也自反。⑵R是對稱的，則r(R)和t(R)也對稱。⑶R是傳遞的，則r(R)也傳遞。證明:⑴因為R自反,由定理5得r(R)=R,即R∪IA=R,r(s(R))=s(R)∪IA=(R∪RC)∪IA=(R∪IA)∪RC=r(R)∪RC=R∪RC=s(R)∴s(R)自反類似可以證明t(R)也自反。證明⑵.證明t(R)對稱:(t(R))C=(R∪R2∪...∪Rn∪...)C=RC∪(R2)C∪...∪(Rn)C∪...=RC∪(RC)2∪...∪(RC)n∪...=R∪R2∪...∪Rn∪...(∵R對稱，∴RC=R)=t(R)所以t(R)也對稱。類似可以證明r(R)也對稱。證明⑶.證明r(R)傳遞:先用歸納法證明下麵結論:(R∪IA)i=IA∪R∪R2∪...∪Ri①i=1時R∪IA=IA∪R結論成立。②假設i≤k時結論成立，即(R∪IA)k=IA∪R∪R2∪...∪Rk(R2)c=(RR)c=RcRc=(Rc)2③當i=k+1時(R∪IA)k+1=(R∪IA)k(R∪IA)=(IA∪R∪R2∪...∪Rk）(IA∪R)=(IA∪R∪R2∪...∪Rk)∪(R∪R2∪...∪Rk+1)=IA∪R∪R2∪...∪Rk∪Rk+1所以結論成立.t(r(R))=t(R∪IA)=(R∪IA)∪(R∪IA)2∪(R∪IA)3∪...=(IA∪R)∪(IA∪R∪R2)∪(IA∪R∪R2∪R3)∪...=IA∪R∪R2∪R3∪...=IA∪t(R)=IA∪R(R傳遞t(R)=R)=r(R)所以r(R)也傳遞。。。定理7：設R1、R2是A上關係，如果R1?R2，則⑴r(R1)?r(R2)⑵s(R1)?s(R2)⑶t(R1)?t(R2)證明⑴r(R1)=IA∪R1?IA∪R2=r(R2)⑵，⑶類似可證。定理8：設R是A上關係，則⑴sr(R)=rs(R)⑵tr(R)=rt(R)⑶st(R)?ts(R)證明：⑴sr(R)=r(R)∪(r(R)c=(R∪IA)∪(R∪IA)c=(R∪IA)∪(Rc∪IAc)=R∪IA∪Rc∪IA=(R∪Rc)∪IA=s(R)∪IA=rs(R)⑵的證明用前邊證明的結論：(R∪IA)k=IA∪R∪R2∪...∪Rk很容易證明，這裏從略。⑶因R?s(R)由定理7得t(R)?ts(R)st(R)?sts(R)因s(R)對稱，有定理6得ts(R)也對稱，由定理5得sts(