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

離散數(shù)學(xué)關(guān)系的閉包由閉包得定義可知,R得自反(對(duì)稱,傳遞)閉包就是含有R并且具有自反(對(duì)稱,傳遞)性質(zhì)得“最小”得關(guān)系。如果R已就是自反得二元關(guān)系,顯然有:R=r(R)。同樣,當(dāng)R就是對(duì)稱得二元關(guān)系時(shí)R=s(R);當(dāng)R就是傳遞得二元關(guān)系時(shí),R=t(R),且反之亦然。二、關(guān)系得閉包運(yùn)算(1)已知一個(gè)集合中得二元關(guān)系R,則

r(R),s(R),t(R)就是唯一得,她就是包含R得最小得自反(對(duì)稱,傳遞)關(guān)系;(2)若R就是自反(對(duì)稱,傳遞)得,則

r(R),s(R),t(R)就就是R本身。(3)若R不就是自反(對(duì)稱,傳遞)得,則可以補(bǔ)上最少序偶,使之變?yōu)樽苑?、?duì)稱、傳遞關(guān)系,從而得到r(R),s(R),t(R);例:設(shè)Ａ={a,b,c},R={<a,b>,<b,c>,<c,a>},求r(R),s(R),t(R)。解:r(R)=s(R)=t(R)={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,<b,b>,<c,c>}例:設(shè)Ａ={a,b},R={<a,a><a,b>},則r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},t(R)={<a,a><a,b>}=R

設(shè)R就是A上得二元關(guān)系,x∈A,將所有(x,x)

R得有序?qū)拥絉上去,使其擴(kuò)充成自反得二元關(guān)系,擴(kuò)充后得自反關(guān)系就就是R得自反閉包r(R)。

例如,A={a,b,c,d},R={(a,a),(b,d),(c,c)}。R得自反閉包r(R)={(a,a),(b,d),(c,c),(b,b),(d,d)}。

于就是可得:定理:R就是A上得二元關(guān)系,則R得自反閉包r(R)=R∪IA。1、構(gòu)造R得自反閉包得方法。

三、閉包得構(gòu)造方法2、構(gòu)造R得對(duì)稱閉包得方法。

每當(dāng)(a,b)∈R,而(b,a)

R時(shí),將有序?qū)?b,a)加到R上去,使其擴(kuò)充成對(duì)稱得二元關(guān)系,擴(kuò)充后得對(duì)稱關(guān)系就就是R得對(duì)稱閉包s(R)。

例如,A={a,b,c,d,e},R={(a,a),(a,b),(b,a),(b,c),(d,e)}。R得對(duì)稱閉包s(R)={(a,a),(a,b),(b,a),(b,c),(c,b),(d,e),(e,d)}。

定理:R是A上二元關(guān)系，是其逆關(guān)系，則R的對(duì)稱閉包s(R)=R∪

。

由逆關(guān)系得定義可知:3、構(gòu)造R得傳遞閉包得方法。

設(shè)R就是A上得二元關(guān)系,每當(dāng)(a,b)∈R與(b,c)∈R而(a,c)

R時(shí),將有序?qū)?a,c)加到R上使其擴(kuò)充成R1,并稱R1

為R得傳遞擴(kuò)張,R1

如果就是傳遞關(guān)系,則R1就是R得傳遞閉包;如果R1不就是傳遞關(guān)系,繼續(xù)求R1得得傳遞擴(kuò)張R2,如果R2就是傳遞關(guān)系時(shí),則R2就是R得傳遞閉包;如果R2不就是傳遞關(guān)系時(shí),繼續(xù)求R2得得傳遞擴(kuò)張R3…,如果A就是有限集,R經(jīng)過(guò)有限次擴(kuò)張后,定能得到R得傳遞閉包。擴(kuò)張后得傳遞關(guān)系就就是R得傳遞閉包t(R)。

定理:設(shè)R為A上得關(guān)系,則有t(R)=R∪R2∪R3∪…

說(shuō)明:對(duì)于有窮集合A(|A|=n)上得關(guān)系,上式中得并最多不超過(guò)Rn、思考:設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求r(R),s(R),t(R)、解:r(R)=R∪R0={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,c>,<c,d>,<d,d>},s(R)=R∪R

1={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>},

t(R)=R∪R2∪R3∪R4

R2={<a,a>,<a,c>,<b,b>,<b,d>}R3={<a,b>,<a,d>,<b,a>,<b,c>}R4={<a,b>,<a,c>,<b,b>,<b,d>}=R2于就是t(R)=R∪R2∪R3=

{<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}、閉包得構(gòu)造方法(續(xù))設(shè)關(guān)系R,r(R),s(R),t(R)得關(guān)系矩陣分別為M,Mr,Ms與Mt,則

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E就是與M同階得單位矩陣,M’就是M得轉(zhuǎn)置矩陣、注意在上述等式中矩陣得元素相加時(shí)使用邏輯加、閉包得構(gòu)造方法(續(xù))設(shè)關(guān)系R,r(R),s(R),t(R)得關(guān)系圖分別記為G,Gr,Gs,Gt,則Gr,Gs,Gt得頂點(diǎn)集與G得頂點(diǎn)集相等、除了G得邊以外,以下述方法添加新邊:

考察G得每個(gè)頂點(diǎn),如果沒(méi)有環(huán)就加上一個(gè)環(huán),最終得到Gr、考察G得每條邊,如果有一條xi到xj得單向邊,i≠j,則在G中加一條xj到xi得反方向邊,最終得到Gs、考察G得每個(gè)頂點(diǎn)xi,找從xi出發(fā)得每一條路徑,如果從xi到路徑中任何結(jié)點(diǎn)xj沒(méi)有邊,就加上這條邊、當(dāng)檢查完所有得頂點(diǎn)后就得到圖Gt、實(shí)例例1設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R與r(R),s(R),t(R)得關(guān)系圖如下圖所示、Rr(R)s(R)t(R)大家學(xué)習(xí)辛苦了，還是要堅(jiān)持繼續(xù)保持安靜定理R就是A上關(guān)系,則⑴R就是自反得,當(dāng)且僅當(dāng)r(R)=R、⑵R就是對(duì)稱得,當(dāng)且僅當(dāng)s(R)=R、⑶R就是傳遞得,當(dāng)且僅當(dāng)t(R)=R、證明略,因?yàn)橛砷]包定義即可得。定理

R就是A上關(guān)系,則⑴R就是自反得,則s(R)與t(R)也自反。⑵R就是對(duì)稱得,則r(R)與t(R)也對(duì)稱。⑶R就是傳遞得,則r(R)也傳遞。證明:⑴因?yàn)镽自反,得r(R)=R,即R∪IA=R,r(s(R))=s(R)∪IA=(R∪R-1)∪IA=(R∪IA)∪R-1=r(R)∪R-1=R∪R-1=s(R)∴s(R)自反

類似可以證明t(R)也自反。證明⑵、證明t(R)對(duì)稱:(t(R))-1=(R∪R2∪、、、∪Rn∪、、、)-1

=R-1∪(R2)-1∪、、、∪(Rn)-1∪、、、

=R-1∪(R-1)2∪、、、∪(R-1)n∪、、、=R∪R2∪、、、∪Rn∪、、、(∵R對(duì)稱,∴R-1=R)=t(R)所以t(R)也對(duì)稱。類似可以證明r(R)也對(duì)稱。證明⑶