譚尚旺， 寧文杰

(中國(guó)石油大學(xué)(華東) 理學(xué)院， 山東 青島266580)

1 引 言

對(duì)集合X上的關(guān)系R和F,令D(R)和C(R)分別表示R的定義域和值域,R°F表示R與F的復(fù)合，Rk表示k個(gè)R的復(fù)合，t(R)表示R的傳遞閉包. 文中未定義的概念和記號(hào)見(jiàn)文獻(xiàn)[1-2].

離散數(shù)學(xué)是信息類學(xué)科的重要基礎(chǔ)課，關(guān)系是離散數(shù)學(xué)的重要內(nèi)容之一. 各類離散數(shù)學(xué)教材都詳細(xì)討論了關(guān)系的閉包運(yùn)算(例如，文獻(xiàn)[1-3]). 在關(guān)系的各種閉包運(yùn)算中以傳遞閉包的計(jì)算最為復(fù)雜和困難. 因此，大量文獻(xiàn)對(duì)傳遞閉包的計(jì)算方法和應(yīng)用進(jìn)行了討論，而關(guān)于傳遍包與關(guān)系其它運(yùn)算之間聯(lián)系的討論則較少. 許多文獻(xiàn)都給出了下面一個(gè)結(jié)論(例如，文獻(xiàn)[1]).

定理1設(shè)R和F是集合X上兩個(gè)關(guān)系，則t(R∪F)?t(R)∪t(F).

由定理1知t(R∪F)?t(R)∪t(F)等價(jià)于t(R∪F)=t(R)∪t(F). 因此，在學(xué)習(xí)離散數(shù)學(xué)課程中，學(xué)生問(wèn)及下面的問(wèn)題：

問(wèn)題1設(shè)R和F是集合X上兩個(gè)關(guān)系，問(wèn)是否存在使t(R∪F)=t(R)∪t(F)成立的非平凡充分必要條件？

受問(wèn)題1的啟發(fā)，學(xué)生進(jìn)一步問(wèn)及下面兩個(gè)問(wèn)題：

問(wèn)題2設(shè)R和F是集合X上兩個(gè)關(guān)系，問(wèn)是否存在使t(R∩F)=t(R)∩t(F)成立的非平凡充分必要條件？

問(wèn)題3設(shè)R和F是集合X上兩個(gè)關(guān)系，問(wèn)是否存在使t(R°F)=t(R)°t(F)成立的非平凡充分必要條件？對(duì)任意正整數(shù)m,是否存在使t(Rm)=[t(R)]m成立的非平凡充分必要條件？

盡管目前離散數(shù)學(xué)教材、教學(xué)參考書和涉及關(guān)系傳遞閉包的論文很多，但遺憾的是沒(méi)有發(fā)現(xiàn)上述問(wèn)題的任何答案. 因此，為解除學(xué)生學(xué)習(xí)上的疑惑和豐富離散數(shù)學(xué)的教學(xué)內(nèi)容，在[4]中已經(jīng)對(duì)問(wèn)題1給出了回答. 本文將利用關(guān)系圖的有關(guān)概念給出問(wèn)題2和問(wèn)題3的回答.

2 結(jié)論及其證明

引理1[1]設(shè)R和F是集合X上兩個(gè)關(guān)系. 如果R?F,則t(R)?t(F).

令GR表示有限集X上關(guān)系R的關(guān)系圖，(a,b)表示GR中起點(diǎn)為a且終點(diǎn)為b的唯一有向邊(特別是(a,a)表示結(jié)點(diǎn)a處的環(huán)).GR中有向邊的序列P=(u0,u1)(u1,u2)…(uk-1,uk)稱為結(jié)點(diǎn)u0到結(jié)點(diǎn)uk的一個(gè)有向通路(簡(jiǎn)稱為通路)，其中P中有向邊的個(gè)數(shù)稱為通路P的長(zhǎng)度. 如果GR中存在結(jié)點(diǎn)x到結(jié)點(diǎn)y的通路，則稱x可達(dá)y,并且記為GR[x→y].

引理3[4]設(shè)R是有限集X上關(guān)系且x,y∈X,則(x,y)∈t(R),當(dāng)且僅當(dāng)GR[x→y].

定理2設(shè)R和F是有限集X上的兩個(gè)關(guān)系，則t(R∩F)=t(R)∩t(F),當(dāng)且僅當(dāng)對(duì)任意的x∈D(R∩F)且y∈C(R∩F),當(dāng)GR[x→y]且GF[x→y]時(shí)，都有GR∩F[x→y].

證用A?B表示命題A成立當(dāng)且僅當(dāng)命題B成立. 由于R∩F?R且R∩F?F,于是由引理1得t(R∩F)?t(R)且t(R∩F)?t(F),從而t(R∩F)?t(R)∩t(F). 因此，依次由子集定義、交運(yùn)算定義和引理3得

t(R∩F)=t(R)∩t(F) ?t(R)∩t(F)?t(R∩F)

?當(dāng)(x,y)∈t(R)∩t(F)時(shí)，都有(x,y)∈t(R∩F)

?當(dāng)(x,y)∈t(R)且(x,y)∈t(F)時(shí)，都有(x,y)∈t(R∩F)

?當(dāng)GR[x→y]且GF[x→y]時(shí)，都有GR∩F[x→y].

例1令X={1,2,3,4,5,6},R和F是X上關(guān)系，其中R,F和R∩F的關(guān)系圖分別如圖1—圖3所示. 顯然，D(R∩F)={1,2,4},C(R∩F)={2,3,5,6}.易發(fā)現(xiàn)GR[2→6]并且GF[2→6],但是GR∩F中2不能到達(dá)6,于是由定理2知t(R∩F)≠t(R)∩t(F).

圖1 GR 圖2 GF 圖3 GR∩F

令R和F是有限集X上的兩個(gè)關(guān)系，x∈D(R)且y∈C(F). 如果GR∪F中存在x到y(tǒng)的一個(gè)通路

Q=(x,x1)(x1,y1)(y1,x2)(x2,y2)(y2,x3)(x3,y3)…(xk-1,yk-1)(yk-1,xk)(xk,y),k≠0,

使Q中的2k個(gè)有向邊分別依次交錯(cuò)的出現(xiàn)在GR和GF中，即

(x,x1),(y1,x2),(y2,x3),…,(yk-1,xk)∈R; (x1,y1),(x2,y2),…,(xk-1,yk-1),(xk,y)∈F,

則稱Q是GR∪F中x關(guān)于GR和GF邊交錯(cuò)到y(tǒng)的通路且稱GR∪F中x關(guān)于GR和GF邊交錯(cuò)可達(dá)y.

定理3設(shè)R和F是有限集X上兩個(gè)關(guān)系，則t(R°F)=t(R)°t(F),當(dāng)且僅當(dāng)R和F滿足下面兩個(gè)條件之一：

C1:C(R)∩D(F)=?；

C2:C(R)∩D(F)≠?,并且對(duì)任意的x∈D(R),y∈C(F),在GR∪F中x關(guān)于GR和GF邊交錯(cuò)可達(dá)y?存在一個(gè)元素z∈C(R)∩D(F),使GR[x→z]且GF[z→y].

證必要性 假設(shè)C1不成立，下面證明C2成立. 令x∈D(R)且y∈C(F),則依次由邊交錯(cuò)可達(dá)定義、邊交錯(cuò)通路定義、關(guān)系復(fù)合定義、引理2和條件t(R°F)=t(R)°t(F)、引理3得

在GR∪F中x關(guān)于GR和GF邊交錯(cuò)可達(dá)y

?GR∪F中存在x關(guān)于GR和GF邊交錯(cuò)到y(tǒng)的通路

(x,x1)(x1,y1)(y1,x2)(x2,y2)(y2,x3)(x3,y3)…(xk-1,yk-1)(yk-1,xk)(xk,y)

?(x,x1),(y1,x2),(y2,x3),…,(yk-1,xk)∈R;(x1,y1),(x2,y2),…,(xk-1,yk-1),(xk,y)∈F

?(x,y1),(y1,y2),(y2,y3),…,(yk-2,yk-1),(yk-1,y)∈R°F

?(x,y)∈(R°F)k?t(R°F)=t(R)°t(F)

?存在元素z∈C(R)∩D(F),使(x,z)∈t(R)且(z,y)∈t(F)

?存在元素z∈C(R)∩D(F),使GR[x→z]且GF[z→y].

充分性 依次由關(guān)系定義域、值域和復(fù)合運(yùn)算定義，容易驗(yàn)證

D(S)=D(t(S)),C(S)=C(t(S)),S∈{R,F};R°F=? ?C(R)∩D(F)=?.

因此，當(dāng)條件C1成立，即C(R)∩D(F)=?時(shí)，t(R°F)=?=t(R)°t(F).

下面設(shè)條件C2成立. 令(x,y)∈t(R°F),則由引理3知GR°F[x→y],于是由結(jié)點(diǎn)可達(dá)的定義知GR°F中存在x到y(tǒng)的一個(gè)通路(x,z1)(z1,z2)(z2,z3)…(zk-1,y),從而由關(guān)系圖的定義知

(x,z1),(z1,z2),(z2,z3),…,(zk-1,y)∈R°F.

由關(guān)系復(fù)合定義知存在元素u1,u2,…,uk∈X,使

(x,u1),(z1,u2),(z2,u3),…,(zk-1,uk)∈R; (u1,z1),(u2,z2),…,(uk-1,zk-1),(uk,y)∈F,

即

(x,u1)(u1,z1)(z1,u2)(u2,z2)(z2,u3)…(uk-1,zk-1)(zk-1,uk)(uk,y)

是GR∪F中x關(guān)于GR和GF邊交錯(cuò)到y(tǒng)的一個(gè)通路. 因此，由假設(shè)條件知存在一個(gè)元素z∈X,使GR[x→z]且GF[z→y],從而由引理3知(x,z)∈t(R),(z,y)∈t(F),進(jìn)而由關(guān)系復(fù)合的定義知(x,y)∈t(R)°t(F). 這就證明了t(R°F)?t(R)°t(F).類似可以證明t(R)°t(F)?t(R°F).因此，t(R°F)=t(R)°t(F).

例2設(shè)X={1,2,3,4,5,6},R和F是X上的兩個(gè)關(guān)系，其中R,F和R∪F的關(guān)系圖分別如圖4—圖6所示. 容易發(fā)現(xiàn)

圖4 GR 圖5 GF 圖6 GR∪F

D(R)={1,2,3,5},C(R)={2,3,4,5}=D(F),C(F)={3,4,5,6}.

顯然，C(R)∩D(F)≠?.D(R)與C(F)的元素共構(gòu)成16個(gè)有序結(jié)點(diǎn)對(duì)，其中

1與2, 2與3, 2與5, 3與4, 5與4, 2與2, 3與3, 5與5

中的每個(gè)有序結(jié)點(diǎn)對(duì)x與y,在GR∪F中顯然沒(méi)有x關(guān)于GR和GF邊交錯(cuò)到y(tǒng)的通路，并且也不存在元素z∈C(R)∩D(F),使GR[x→z]并且GF[z→y].

令PJ[x,y]表示GR∪F中x關(guān)于GR和GF邊交錯(cuò)到y(tǒng)的一個(gè)通路，PR[x,y]表示GR中x到y(tǒng)的一個(gè)通路，則對(duì)有序結(jié)點(diǎn)對(duì)

1與3, 1與4, 1與5, 1與6, 2與4, 2與6, 3與6, 5與6,

有

因此，R和F滿足定理3的條件C2，于是由定理3知t(R°F)=t(R)°t(F).

引理4設(shè)R是有限集X上關(guān)系，則對(duì)整數(shù)m≥2,都有t(Rm)?[t(R)]m.

證令(x,y)∈t(Rm),則由引理2知存在正整數(shù)k,使(x,y)∈(Rm)k=Rmk. 由關(guān)系復(fù)合定義知存在元素x1,x2,…,xmk-1∈X,使

(x,x1),(x1,x2),…,(xmk-2,xmk-1),(xmk-1,y)∈R.

因此，由關(guān)系圖的定義知

(x,x1)(x1,x2)…(xm-2,xm-1)(xm-1,xm)…(xmk-2,xmk-1)(xmk-1,y)

是GR中x到y(tǒng)的一個(gè)通路，從而

GR[x→x1],GR[x1→x2],…,GR[xm-2→xm-1],GR[xm-1→y].

由引理3得

(x,x1),(x1,x2),…,(xm-2,xm-1),(xm-1,y)∈t(R).

于是由關(guān)系復(fù)合的定義知(x,y)∈[t(R)]m. 這就證明了結(jié)論t(Rm)?[t(R)]m.

定理4設(shè)R是有限集X上關(guān)系且m≥2,則t(Rm)=[t(R)]m,當(dāng)且僅當(dāng)對(duì)任意的x∈D(R)且y∈C(R),當(dāng)GR中存在x到y(tǒng)長(zhǎng)≥m+1的通路時(shí)，GR中都存在x到y(tǒng)長(zhǎng)為m正整數(shù)倍的通路.

證必要性 令

(x,x1)(x1,x2)…(xm-2,xm-1)(xm-1,xm)…(xs-2,xs-1)(xs-1,y)

是GR中x到y(tǒng)的長(zhǎng)為s(s≥m+1)的通路，則

GR[x→x1],GR[x1→x2],…,GR[xm-2→xm-1],GR[xm-1→y].

由引理3知

(x,x1),(x1,x2),…,(xm-2,xm-1),(xm-1,y)∈t(R).

由關(guān)系復(fù)合的定義知(x,y)∈[t(R)]m. 由假設(shè)條件t(Rm)=[t(R)]m知(x,y)∈t(Rm). 由引理2知存在正整數(shù)k,使(x,y)∈(Rm)k=Rmk. 由關(guān)系復(fù)合定義知存在元素z1,z2,…,zmk-1∈X,使

(x,z1),(z1,z2),…,(zmk-2,zmk-1),(zmk-1,y)∈R.

于是由關(guān)系圖定義知

(x,z1)(z1,z2)…(zmk-2,zmk-1)(zmk-1,y)

是GR中x到y(tǒng)的長(zhǎng)為km的通路.

充分性 令(x,y)∈t(R)m,則由關(guān)系復(fù)合的定義知存在元素x1,x2,…,xm-1∈X,使

(x0,x1),(x1,x2),…,(xm-2,xm-1),(xm-1,xm)∈t(R), 其中x0=x,xm=y.

由引理3知

GR[x0→x1],GR[x1→x2],…,GR[xm-1→xm].

令Pi表示GR中xi到xi+1的一個(gè)通路，則P0P1…Pm-1是GR中x到y(tǒng)的一個(gè)長(zhǎng)為s(s≥m)的通路. 不妨設(shè)s≥m+1(否則，下面的k取1)，則由假設(shè)條件知GR中存在x到y(tǒng)的長(zhǎng)為km的通路

(x,z1)(z1,z2)…(zmk-2,zmk-1)(zmk-1,y),

這等價(jià)于

(x,z1),(z1,z2),…,(zmk-2,zmk-1),(zmk-1,y)∈R.

于是由關(guān)系復(fù)合得定義知(x,y)∈Rkm=(Rm)k,從而由引理2知(x,y)∈t(Rm). 這就證明了t(Rm)?[t(R)]m. 因此，由引理4知t(Rm)=[t(R)]m.

推論1設(shè)R是有限集X上自反的關(guān)系，則對(duì)整數(shù)m≥2,都有t(Rm)=[t(R)]m.

證令

Q=(x,x1)(x1,x2)…(xs-2,xs-1)(xs-1,y)

推論2設(shè)R是有限集X上傳遞的關(guān)系，則對(duì)整數(shù)m≥2,都有t(Rm)=[t(R)]m.

證令

(x,x1)(x1,x2)…(xm-2,xm-1)(xm-1,xm)…(xs-2,xs-1)(xs-1,y)

是GR中結(jié)點(diǎn)x到結(jié)點(diǎn)y的長(zhǎng)為s(s≥m+1)的通路，則

(x,x1),(x1,x2),…,(xm-2,xm-1),(xm-1,xm),…,(xs-2,xs-1),(xs-1,y)∈R.

既然R是傳遞的，于是(xm-1,y)∈R,從而(x,x1)(x1,x2)…(xm-2,xm-1)(xm-1,y)是GR中x到y(tǒng)的長(zhǎng)為m的通路. 因此，由定理4知t(Rm)=[t(R)]m.

設(shè)R是n(n≥3)元集合X上的關(guān)系且GR是有向樹. 由有向樹的定義知R是反自反、反對(duì)稱、反傳遞的，并且當(dāng)GR[x→y]時(shí)，x到y(tǒng)的通路是唯一的且是基本通路. 用l(R)表示GR中最長(zhǎng)通路的長(zhǎng)度，則1≤l(R)≤n-1. 如果l(R)=1,則存在a∈X,使得R={(a,b)∶b∈X-{a}}或者R={(b,a)∶b∈X-{a}},此時(shí)對(duì)任意整數(shù)m≥2,容易發(fā)現(xiàn)都有t(Rm)=?=[t(R)]m.

推論3設(shè)R是有限集合X上的關(guān)系，其中GR是有向樹并且l(R)≥2,則當(dāng)m≥l(R)時(shí)，都有t(Rm)=[t(R)]m,當(dāng)2≤m

證當(dāng)m≥l(R)時(shí)，對(duì)任意的x,y∈X,由l(R)定義知GR中沒(méi)有x到y(tǒng)的長(zhǎng)≥m+1的通路，于是由定理4知t(Rm)=[t(R)]m. 當(dāng)2≤m

3 結(jié) 論

利用關(guān)系圖的有關(guān)概念解決了各類離散數(shù)學(xué)教材中傳遞閉包的幾個(gè)遺留問(wèn)題，即確定了有限集合X上關(guān)系R和F分別滿足

t(R∩F)=t(R)∩t(F),t(R°F)=t(R)°t(F),t(Rm)=[t(R)]m

的充分必要條件. 特別是當(dāng)R是自反的或傳遞的時(shí)證明了t(Rm)=[t(R)]m成立，并且當(dāng)GR是有向樹時(shí)也確定了使t(Rm)=[t(R)]m成立的m的所有取值(該結(jié)論顯然當(dāng)GR是有向森林時(shí)也成立). 這些結(jié)論揭示了關(guān)系傳遞閉包與關(guān)系交與復(fù)合運(yùn)算之間的內(nèi)在聯(lián)系，有助于學(xué)生理解關(guān)系的運(yùn)算性質(zhì)和應(yīng)用，豐富了離散數(shù)學(xué)的教學(xué)內(nèi)容.

致謝作者感謝相關(guān)文獻(xiàn)對(duì)本文的啟發(fā)以及審稿專家提出的寶貴意見(jiàn)！