離散數(shù)學(xué)(第11講)關(guān)系2

1、欒新成欒新成 四川大學(xué)軟件學(xué)院四川大學(xué)軟件學(xué)院85997822 1380802408185997822第5章章 二元關(guān)系二元關(guān)系(2)主要內(nèi)容主要內(nèi)容v 二元關(guān)系的閉包二元關(guān)系的閉包2022年年3月月22日日2二元關(guān)系的閉包二元關(guān)系的閉包v 設(shè)設(shè)R是是A上的關(guān)系，我們希望上的關(guān)系，我們希望R具有某些有用的性質(zhì)，比具有某些有用的性質(zhì)，比如如自反性、對(duì)稱性、傳遞性自反性、對(duì)稱性、傳遞性等。如果等。如果R不具有這些性質(zhì)，不具有這些性質(zhì)，可以通過(guò)在可以通過(guò)在R中添加一些中添加一些有序?qū)τ行驅(qū)?lái)改造來(lái)改造R，得到新關(guān)系，得到新關(guān)系R，使使R具有上述性質(zhì)，但又不希望具有上述性質(zhì)，

2、但又不希望R與與R相差太多，即相差太多，即添加添加的有序?qū)Φ挠行驅(qū)σM可能的少，滿足這些要求的要盡可能的少，滿足這些要求的R就稱為就稱為R的閉的閉包。包。2022年年3月月22日日3二元關(guān)系的閉包二元關(guān)系的閉包v 定義定義4-4.1設(shè)設(shè)R是定義在是定義在A上的二元關(guān)系，若存在上的二元關(guān)系，若存在A上上的關(guān)系的關(guān)系R滿足：滿足：1) R是自反的是自反的(或?qū)ΨQ的、或可傳遞的或?qū)ΨQ的、或可傳遞的)，2) R R，3) 對(duì)對(duì)A上任何其它滿足上任何其它滿足1）和）和2）的關(guān)系）的關(guān)系R，則：，則： R R。（表明。（表明R的最小性）的最小性）v 則稱則稱R為為R的自反閉包的自反閉包(或?qū)ΨQ閉包、或傳遞

3、閉包或?qū)ΨQ閉包、或傳遞閉包)。 R的的自反閉包、對(duì)稱閉包、傳遞閉包分別記為自反閉包、對(duì)稱閉包、傳遞閉包分別記為r(R)、s(R)和和t(R)。2022年年3月月22日日4二元關(guān)系的閉包二元關(guān)系的閉包v 例例4.14v 設(shè)集合設(shè)集合Aa,b,c,R,是定義在是定義在A上的二元關(guān)系，求上的二元關(guān)系，求r(R),s(R),t(R),并畫出并畫出R,r(R),s(R),t(R)的關(guān)系圖和求出相應(yīng)的關(guān)系矩陣。的關(guān)系圖和求出相應(yīng)的關(guān)系矩陣。v 解：解：v r(R),；v s(R),；v t(R),。2022年年3月月22日日5二元關(guān)系的閉包二元關(guān)系的閉包2022年年3月月22日日6000110110,01

4、0111010,100110011,000110010)()()(RtRsRrRMMMM二元關(guān)系的閉包二元關(guān)系的閉包v 例例v 求下列關(guān)系的求下列關(guān)系的r(R)、s(R)、t(R)：v (1)整數(shù)集整數(shù)集Z上的上的“”關(guān)系關(guān)系v (2)整數(shù)集整數(shù)集Z上的上的“=”關(guān)系關(guān)系v 解解: v (1)Z上的上的“”關(guān)系的關(guān)系的r(R)為為“”；s(R)為為“ ”；v t(R)為為“”v (2)Z上的上的“=”關(guān)系的關(guān)系的r(R)為為“=”；s(R)為為“ =”；v t(R)為為“=”2022年年3月月22日日7利用關(guān)系圖和關(guān)系矩陣求閉包利用關(guān)系圖和關(guān)系矩陣求閉包求一個(gè)關(guān)系的自反閉包，即將圖中的所有無(wú)環(huán)

5、的節(jié)點(diǎn)加上環(huán)；求一個(gè)關(guān)系的自反閉包，即將圖中的所有無(wú)環(huán)的節(jié)點(diǎn)加上環(huán)；關(guān)系矩陣中對(duì)角線上的值關(guān)系矩陣中對(duì)角線上的值rij全變?yōu)槿優(yōu)椤?”。求一個(gè)關(guān)系的對(duì)稱閉包，則在圖中，任何一對(duì)節(jié)點(diǎn)之間，若求一個(gè)關(guān)系的對(duì)稱閉包，則在圖中，任何一對(duì)節(jié)點(diǎn)之間，若僅存在一條邊，則加一條方向相反的另一條邊；關(guān)系矩陣僅存在一條邊，則加一條方向相反的另一條邊；關(guān)系矩陣中則為：若有中則為：若有rij1(ij)，則令，則令rji1(若若rji1),即即Ms(R)MRMR-1。求一個(gè)關(guān)系的傳遞閉包，則在圖中，對(duì)任意節(jié)點(diǎn)求一個(gè)關(guān)系的傳遞閉包，則在圖中，對(duì)任意節(jié)點(diǎn)a,b,c,若若a到到b有一條邊，同時(shí)有一條邊，同時(shí)b到到c也有一條

6、邊，則從也有一條邊，則從a到到c必增加一必增加一條邊條邊(當(dāng)當(dāng)a到到c無(wú)邊時(shí)無(wú)邊時(shí))；在關(guān)系矩陣中，若；在關(guān)系矩陣中，若rij1，rjk1,則令則令rik1(若若rik1)。2022年年3月月22日日8利用關(guān)系運(yùn)算求閉包利用關(guān)系運(yùn)算求閉包v 定理定理4-4.1v 設(shè)設(shè)R是集合是集合A上的二元關(guān)系，則：上的二元關(guān)系，則： 1) r(R)RIA。 2) s(R)RR-1。 3) t(R)v 證明證明3）可采用二種方法，一種是證明）可采用二種方法，一種是證明是傳遞閉包是傳遞閉包（按定義證明）；一種是直接證明（按定義證明）；一種是直接證明 t(R)(書上采用書上采用的方法）。的方法）。2022年年3月

7、月22日日9Ri1i Ri1i Ri1i 利用關(guān)系運(yùn)算求閉包利用關(guān)系運(yùn)算求閉包v 方法一、設(shè)方法一、設(shè)R R1 1(1)顯然顯然R =R1 1 。(2)對(duì)任意對(duì)任意a,b,cA，若，若R1 1，R1 1,則由則由R1，必存在，必存在Rj j,Rk k(1j,k )，使得，使得Rj j，Rk k，即，即Rj+kj+k(1j+k ), Rj+kj+k R1,所以所以R1，即，即R1是傳遞的。是傳遞的。(3)設(shè)設(shè)R2是是R的任何一個(gè)關(guān)系，且有的任何一個(gè)關(guān)系，且有R R2 AA，R2是傳是傳遞的。對(duì)任意遞的。對(duì)任意R1，存在，存在Rj j(1j )，使得，使得Rj j，所以存在，所以存在c1,c2,c

8、3,cj-1A，使得：，使得：2022年年3月月22日日10Ri1i Ri1i Ri1i Ri1i 利用關(guān)系運(yùn)算求閉包利用關(guān)系運(yùn)算求閉包v R,R,R,.,R。v 因因R R2，所以，所以v R2,R2,R2,R2。v 由由R2是傳遞的，有：是傳遞的，有：v R2,R2,R2,R2。v 一直下去，最終有：一直下去，最終有：R2。v 所以，所以，R1 R2。v 由由(1),(2),(3)知：知：R1是是R的傳遞閉包，即的傳遞閉包，即t(R) 2022年年3月月22日日11Ri1i 利用關(guān)系運(yùn)算求閉包利用關(guān)系運(yùn)算求閉包v 方法二、設(shè)方法二、設(shè)t(R)是是R的傳遞閉包，證明的傳遞閉包，證明t(R)

9、。v (1)證明證明t(R) ，v 是可傳遞，同時(shí)是可傳遞，同時(shí)R v 由傳遞閉包的定義知：由傳遞閉包的定義知： t(R) 。v (2)證明證明 t(R)。只需證對(duì)任意的。只需證對(duì)任意的iN+,有有Ri t(R)。v 當(dāng)當(dāng)i1時(shí)，因時(shí)，因R t(R),顯然成立。顯然成立。v 設(shè)設(shè)ik時(shí)，有時(shí)，有Rk t(R)成立。成立。v 當(dāng)當(dāng)ik+1時(shí)，對(duì)任意時(shí)，對(duì)任意Rk+1，則存在，則存在cA，使得，使得Rk，R，由歸納假設(shè)有：，由歸納假設(shè)有：t(R)，t(R)，由，由t(R)可可傳遞，所以傳遞，所以t(R)，v 即有：即有：Rk+1 t(R)。2022年年3月月22日日12Ri1i Ri1i Ri1i

10、 Ri1i Ri1i Ri1i 利用關(guān)系運(yùn)算求閉包利用關(guān)系運(yùn)算求閉包v 由歸納法知，對(duì)任意有的由歸納法知，對(duì)任意有的iN+,有有Ri t(R)。所以。所以v t(R)。v 由由(1)、(2)知：知：t(R) 。 2022年年3月月22日日13Ri1i Ri1i Warshall算法算法v 定理定理4-4.2v 設(shè)設(shè)A是是n個(gè)元素的集合，個(gè)元素的集合，R是集合是集合A上的二元關(guān)系，則上的二元關(guān)系，則 正正整數(shù)整數(shù)k，kn，使，使t(R) 。v 用矩陣計(jì)算傳遞閉包用矩陣計(jì)算傳遞閉包-Warshall(1962)算法算法v (為計(jì)算機(jī)解決此類問(wèn)題奠定了基礎(chǔ)為計(jì)算機(jī)解決此類問(wèn)題奠定了基礎(chǔ))v 設(shè)設(shè)R是

11、集合上的二元關(guān)系是集合上的二元關(guān)系,Mr是是R的關(guān)系矩陣的關(guān)系矩陣v (1)置新矩陣置新矩陣A:=Mrv (2)置置(列列) i:=12022年年3月月22日日141kiiRWarshall算法算法v (3) 對(duì)所有的對(duì)所有的j(1jn) v 如如A(j,i)=1,則對(duì)則對(duì)k=1,2,nv A(j,k):=A(j,k) A(i,k)v (即將即將A的第的第j行與行與A的第的第i行進(jìn)行邏輯加后送回行進(jìn)行邏輯加后送回A的第的第j行行)v (4)i:=i+1v (5)如如in轉(zhuǎn)轉(zhuǎn)(3),否則停止。否則停止。2022年年3月月22日日15Warshall算法算法v 例例4.15v 設(shè)設(shè)R=,v i:=

12、1; i=1時(shí)時(shí),A的第一列中只有的第一列中只有A(1,1)=1,將將A的第一行的第一行上元素與本身作邏輯加上元素與本身作邏輯加,結(jié)果送該行結(jié)果送該行,A不變。不變。v i:=i+1; i=2,A的第二列有兩個(gè)的第二列有兩個(gè)1,即即A(1,2)=A(3,2)=1 2022年年3月月22日日160000101001000 0 1 1 MWarshall算法算法v 分別將分別將A的第的第1行和第行和第3行與第二行對(duì)應(yīng)元素作邏輯加行與第二行對(duì)應(yīng)元素作邏輯加,將將結(jié)果分別送結(jié)果分別送1,3行得行得: 2022年年3月月22日日170 0001 11001000 1 1 10000101001000 0

13、 1 1 MWarshall算法算法v i:=i+1; i=3,A的第的第3列有列有3個(gè)個(gè)1,即即A(1,3)=A(2,3)=A(3,3)=1,v 分別將分別將A的第的第1,2,3行與第行與第3行對(duì)應(yīng)元素作邏輯加行對(duì)應(yīng)元素作邏輯加,將結(jié)果將結(jié)果分別送分別送1,2,3行得行得:2022年年3月月22日日180 0001 1101 1101 1 1 10 0001 11001000 1 1 1 MWarshall算法算法v i:=i+1; i=4,A的第的第4行全為行全為0,A不變。不變。v i:=i+1; i=54=n,停止停止,即得即得:v 在關(guān)系矩陣中，每列（結(jié)點(diǎn)）的每個(gè)等于在關(guān)系矩陣中，每

14、列（結(jié)點(diǎn)）的每個(gè)等于1的元素反映的的元素反映的是該元素所在行（結(jié)點(diǎn)）到該結(jié)點(diǎn)有一條有向邊；每行是該元素所在行（結(jié)點(diǎn)）到該結(jié)點(diǎn)有一條有向邊；每行（結(jié)點(diǎn)）的每個(gè)等于（結(jié)點(diǎn)）的每個(gè)等于1的元素反映的是該結(jié)點(diǎn)到該元素所的元素反映的是該結(jié)點(diǎn)到該元素所在列（結(jié)點(diǎn)）有一條有向邊。在列（結(jié)點(diǎn)）有一條有向邊。2022年年3月月22日日190 0001 1101 1101 1 1 1 MRWarshall算法的基本思想算法的基本思想v 因此，對(duì)每個(gè)結(jié)點(diǎn)（從第一列開始），找出所有具有到此因此，對(duì)每個(gè)結(jié)點(diǎn)（從第一列開始），找出所有具有到此結(jié)點(diǎn)的有向邊的結(jié)點(diǎn)，再將這些結(jié)點(diǎn)所在行同該結(jié)點(diǎn)所在結(jié)點(diǎn)的有向邊的結(jié)點(diǎn)，再將這些結(jié)

15、點(diǎn)所在行同該結(jié)點(diǎn)所在行進(jìn)行邏輯加后作為結(jié)點(diǎn)所在的新行（添加新的有向邊）行進(jìn)行邏輯加后作為結(jié)點(diǎn)所在的新行（添加新的有向邊）（反映了如果這些結(jié)點(diǎn)沒有到其它結(jié)點(diǎn)的有向邊，但有到（反映了如果這些結(jié)點(diǎn)沒有到其它結(jié)點(diǎn)的有向邊，但有到該結(jié)點(diǎn)的有向邊，再通過(guò)該結(jié)點(diǎn)間接到達(dá)其它結(jié)點(diǎn)，根據(jù)該結(jié)點(diǎn)的有向邊，再通過(guò)該結(jié)點(diǎn)間接到達(dá)其它結(jié)點(diǎn)，根據(jù)傳遞閉包的定義，這些結(jié)點(diǎn)就必然有一條有向邊到達(dá)其它傳遞閉包的定義，這些結(jié)點(diǎn)就必然有一條有向邊到達(dá)其它結(jié)點(diǎn)）。結(jié)點(diǎn)）。2022年年3月月22日日201 13 32 24 45 5閉包運(yùn)算的性質(zhì)閉包運(yùn)算的性質(zhì)v 定理定理4-4.3 設(shè)設(shè)R1，R2是集合是集合A上的關(guān)系，且上的關(guān)系，且

16、R1 R2，則：，則：v 1)r(R1) r(R2)v 2)s(R1) s(R2)v 3)t(R1) t(R2)v 定理定理4-4.4 設(shè)設(shè)R是集合是集合A上的關(guān)系，則：上的關(guān)系，則：v 若若R是自反的，則是自反的，則s(R),t(R)也是自反的也是自反的v 若若R是對(duì)稱的，則是對(duì)稱的，則r(R),t(R)也是對(duì)稱的也是對(duì)稱的v 若若R是傳遞的，則是傳遞的，則r(R)也是傳遞的也是傳遞的2022年年3月月22日日21多重閉包多重閉包v 定義定義4-4.2v 1) 集合集合A上的關(guān)系的自反對(duì)稱閉包定義為上的關(guān)系的自反對(duì)稱閉包定義為rs(R)r(s(R)v 2) 集合集合A上的關(guān)系的自反傳遞閉包定義為上的關(guān)系的自反傳遞閉包定義為rt(R)r(t(R)v 3) 集合集合A上的關(guān)系的對(duì)稱傳遞閉包定義為上的關(guān)系的對(duì)稱傳遞閉包定義為st(R)s(t(R)v 同上，我們還可定義同上，我們還可定義sr(R),tr(R),ts(R),v 定理定理4-4.5設(shè)設(shè)R是集合是集合A上的關(guān)系，則：上的關(guān)系，則：v 1) rs(R)sr(R)v 2) rt(R)tr(R)v 3) st(R) ts(R)2022年年3月月22日日22多重閉包多重閉包v 例例4.16v 設(shè)設(shè)A1,2,R,則：則：v st(R)s(