離散數(shù)學(xué) 關(guān)系的閉包ppt課件

1、.1，4.4關(guān)系的閉包，定義閉包的構(gòu)造方法集合是表示閉包特性的矩陣表示，2，1，閉包定義，非空集a的R的關(guān)系定義，R的自反轉(zhuǎn)(對(duì)稱或傳遞)閉包與a的關(guān)系R，R滿足以下條件：(1) r表示包含自身反轉(zhuǎn)(對(duì)稱或傳遞)(2) RR (3) a中的r的所有自身反轉(zhuǎn)(對(duì)稱或傳遞)關(guān)系r的RR。通常，將R的自反轉(zhuǎn)閉包記錄為r(R)，將對(duì)稱閉包記錄為s(R)，將傳輸閉包記錄為t (r)，(3，從閉包的定義中可以看出，R的自反射(對(duì)稱，傳遞)閉包包含R，具有自反射(對(duì)稱，傳遞)特性如果R已經(jīng)是反射二進(jìn)制關(guān)系，則R=r(R)。同樣，如果r是對(duì)稱的二進(jìn)制關(guān)系，則r=s(r)；如果R是傳遞的二進(jìn)制關(guān)系，則R=t(R

2、)，反之亦然。4，2，關(guān)系的閉包運(yùn)算，(1)如果知道集的二進(jìn)制關(guān)系R，則r(R)，s(R)，t(R)是唯一且包含R的最小自反轉(zhuǎn)(對(duì)稱，傳遞)關(guān)系。(2) r為反射(對(duì)稱，傳遞)時(shí)，r(R)、s(R)、t(R)為R本身。(3)如果r不是自反轉(zhuǎn)(對(duì)稱，傳遞)，則可以補(bǔ)充最小順序?qū)?，使其成為自?dòng)、對(duì)稱、傳遞關(guān)系，從而得到r、s (r)、t (r)。5，例如，設(shè)置a=a，b，c，r=，r(R)，s(R)，t(R)。解決方案：r(R)=，s (r)=，t (r)=，例如a=a，6，r設(shè)置為a的二進(jìn)制關(guān)系，x-a，將所有(x，x) r的排序?qū)μ砑拥絩，以擴(kuò)展到其自身的二進(jìn)制關(guān)系，例如，a=a，b，c，d，

3、r=(a，x)r的自反轉(zhuǎn)閉包r (r)=(a，a)，(b，d)，(c，c)，(b，b)，(d，d)?？梢缘玫剑憾ɡ恚?R是a的二進(jìn)制關(guān)系，R的自閉包R(R)=Ria。1 .構(gòu)造r的自閉包的方法。第三，閉包的構(gòu)成方法，7，2。構(gòu)造r的對(duì)稱閉包的方法。只要R成為(a，b)，例如，a=a，b，c，d，e，r=(a，a)，(a，b)，(b，a)，(b，c)，r的鏡像閉包s (r)=(a，a)，(a，b)，(b，a)，(b，c)，(c，b)，(d，e)，定理3360 R是a的二進(jìn)制關(guān)系，如果是反向關(guān)系，則R的對(duì)稱閉包s (r)=r ?？梢酝ㄟ^(guò)反向關(guān)系的定義知道：8、3。配置r的傳遞閉包的方法。將R設(shè)置為

4、a的二進(jìn)制關(guān)系，將(a，b)R和(b，c)R和(a，c) r添加到R以擴(kuò)展到R1，R1稱為R的傳遞擴(kuò)展，如果R1是傳遞關(guān)系，則R1是R的傳遞閉包。如果R1不是傳播關(guān)系，則繼續(xù)查找R1的傳播擴(kuò)展R2，如果R2是傳播關(guān)系，則R2是r的傳播閉包。R2的傳播擴(kuò)展R3(如果R2不是傳播關(guān)系).如果a是限制集，那么r在限制擴(kuò)展后可以得到r的傳遞閉包。擴(kuò)展的傳遞關(guān)系是R的傳遞閉包t(R)。，定理3360將r設(shè)置為a的關(guān)系，t(r)=rR2R3.說(shuō)明：關(guān)于窮集A (|A|=n)的關(guān)系，常識(shí)是Rn .9，事故：a=a，b，c，d，r=，r(R)，s(R)，t(R)，解決方案3330R1=，t(r)=r-R2-R

5、3-R4，R2=，R3=，R3=，。10，構(gòu)造閉包的方法(續(xù))，關(guān)系r，r，s (r)，t (r)的關(guān)系矩陣分別為M，Mr，Ms，Mt時(shí)Mr=m e ms=m mt.e是與M相同的單位矩陣，M 是M的轉(zhuǎn)換矩陣。在上述方程中，矩陣的元素相加時(shí)的邏輯相加。11，注意閉包的構(gòu)造方法(續(xù))，關(guān)系設(shè)置R、R、s、t(R)的關(guān)系圖分別與g、gr、gt、g、gt的頂點(diǎn)集相同。除了g的角外，使用以下方法添加新邊：檢查g的每個(gè)頂點(diǎn)，如果沒(méi)有環(huán)，則添加環(huán)，最終搜索Gr. g的每個(gè)邊，如果存在從Xi到XJ的單向邊，則將I-j添加到g的XJ到Xi的相反方向，然后檢查gs.g的每個(gè)頂點(diǎn)Xi，以查找從Xi出發(fā)的每個(gè)路徑。

6、如果從Xi到路徑中的節(jié)點(diǎn)XJ沒(méi)有邊，請(qǐng)?zhí)砑哟诉?。檢查所有頂點(diǎn)后，圖形gt。12，示例1顯示了A=a，b，c，d，R=，R與r(R)、s(R)、t(R)的關(guān)系圖，如下圖所示r、r、s (r)、t (r)和南寧空調(diào)回收南寧空調(diào)。用戶可以在投影儀或計(jì)算機(jī)上進(jìn)行演示，打印演示文稿，將其制作成膠片，并應(yīng)用于更廣泛的領(lǐng)域。使用Microsoft Office PowerPoint，您不僅可以創(chuàng)建演示文稿，還可以直接在internet上舉行面對(duì)面會(huì)議、遠(yuǎn)程會(huì)議或向觀眾演示演示文稿。Microsoft Office PowerPoint支持PPT、pptx以等格式創(chuàng)建的演示文稿?；騪df、圖片格式等。14，如

7、果清理R為a相關(guān)系，則930；R是反射的，僅r (r)=R. r (r)是對(duì)稱的，并且僅傳遞s (r)=r. r (r)，則和t (r)=R. r (r)如果定理R是a相關(guān)系，則930；R是磁反，s(R)和t(R)也是磁反。如果R是對(duì)稱的，則r(R)和t(R)也是對(duì)稱的。如果傳遞了R，則r(R)也將傳遞。證明： 93360 93360；R(R)=R，即R-ia=R，R(s)=s(R)-ia=(R-R-R-)r-1=r(r)8746；r-1=r-1=s(r)-s(r)相反。15一樣，可以在t(R)中反向證明。證明t(R)對(duì)稱：(t(R)-1=(RR2rn.)-1=r-1=r-1-1(rn)-1.

8、=r-1；(r-1) 2.(r-1)n；=r-R2-rn.(R對(duì)稱，R對(duì)稱一樣，可以證明r(R)也是對(duì)稱的。證明(r)證明(r)傳遞(r):首先用歸納法證明以下結(jié)論.riI=1點(diǎn)ria=iar結(jié)論。Ik是(ria)k=iarR2rk，16，I=k 1:00(ria)k 1=(ria)k(ria)=(iarR2K6；rk(ia r)=(ia r 2 8746；rk)rR2rR2rk 1因此得出結(jié)論。t(r)ia(22(r)ia)3.=(ia r R2)(ia r R2 R3).=ia-R(R)=ia-R(R)=R(R)。17，定理將R1，R2設(shè)置為a相關(guān)系，對(duì)于R1 R2，則為r(R1)r(R2)s(R2)s(R1)t(R2)證明清理將r稱為a相關(guān)系，然后 33；Sr(r)=RS(r) tr(r)=rt(r)ts(r)證明： 33；Sr(r)=r，18，原因RS (r)，t(r)t