離散數(shù)學(xué)教材中傳遞閉包的兩個問題

譚尚旺， 寧文杰

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

1 引 言

文中未定義的概念和記號見文獻(xiàn)[1].離散數(shù)學(xué)是信息類學(xué)科的重要基礎(chǔ)課，關(guān)系是離散數(shù)學(xué)的重要內(nèi)容之一.各類離散數(shù)學(xué)教材都詳細(xì)討論了關(guān)系的各種閉包運算(例如，文獻(xiàn)[1-3]).

對集合X上的關(guān)系R和S，令E(R)表示R的定義域D(R)和值域C(R)的并集，R°S表示R與S的復(fù)合，Rk表示k個R的復(fù)合，t(R)表示R的傳遞閉包，s(R)表示R的對稱閉包.許多離散數(shù)學(xué)教材都給出了下面兩個結(jié)論(例如，文獻(xiàn)[3, P40-44]).

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

定理2設(shè)R是集合X上的一個關(guān)系，則t(s(R))?s(t(R)).

由定理1容易發(fā)現(xiàn)t(R1∪R2)?t(R1)∪t(R2) 等價于t(R1∪R2)=t(R1)∪t(R2) ；由定理2容易發(fā)現(xiàn)t(s(R))?s(t(R))等價于t(s(R))=s(t(R)).因此，在學(xué)習(xí)離散數(shù)學(xué)課程中，受定理1和定理2的啟發(fā)，學(xué)生問及下面兩個問題：

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

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

盡管離散數(shù)學(xué)教材、教學(xué)參考書和涉及關(guān)系傳遞閉包的論文繁多，但遺憾的是沒有發(fā)現(xiàn)上面兩個問題的任何答案.鑒于此，為了解除學(xué)生學(xué)習(xí)上的疑惑和豐富離散數(shù)學(xué)的教學(xué)內(nèi)容，本文將利用關(guān)系圖的有關(guān)概念給出兩個問題在有限集情形下的回答.

2 結(jié)論及其證明

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

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

證用A?B表示命題A成立的充分必要條件是命題B成立.依次由引理1、關(guān)系復(fù)合運算的定義、關(guān)系圖和有向通路的定義、結(jié)點可達(dá)的定義得

(x,y)∈t(R)?存在一個正整數(shù)k，使得(x,y)∈Rk

?存在v1,v2,…,vk-1∈X，使得(x,v1),(v1,v2),…,(vk-1,y)∈R

?(x,v1)(v1,v2)…(vk-1,y)是GR中x到y(tǒng)的一個有向通路

?GR[x→y].

引理3設(shè)R1和R2是有限集X上的兩個關(guān)系，則t(R1∪R2)=t(R1)∪t(R2)，當(dāng)且僅當(dāng)對任意的x,y∈E(R1∪R2)，當(dāng)GR1∪R2[x→y]時，都有GR1[x→y]或GR2[x→y].

證依次由定理1、子集的定義、并運算的定義、引理2得

t(R1∪R2)=t(R1)∪t(R2)?t(R1∪R2)?t(R1)∪t(R2)

?當(dāng)(x,y)∈t(R1∪R2)時，都有(x,y)∈t(R1)∪t(R2)

?當(dāng)(x,y)∈t(R1∪R2)時，都有(x,y)∈t(R1)或(x,y)∈t(R2)

?當(dāng)GR1∪R2[x→y]時，都有GR1[x→y]或GR2[x→y].

定理3設(shè)R1和R2是有限集X上的兩個關(guān)系，記

J(R1,R2)=[C(R1)∩D(R2)]∪[C(R2)∩D(R1)]，

則t(R1∪R2)=t(R1)∪t(R2)，當(dāng)且僅當(dāng)R1和R2滿足下面兩個條件之一：

C1:J(R1,R2)=?；

C2:J(R1,R2)≠?，并且z∈J(R1,R2),x,y∈E(R1∪R2)滿足GR1[x→z]且GR2[z→y]或者GR2[x→z]且GR1[z→y]時，都有GR1[x→y]或GR2[x→y].

證必要性. 設(shè)t(R1∪R2)=t(R1)∪t(R2).

假設(shè)條件C1不成立，即J(R1,R2)≠?.令z∈J(R1,R2),x,y∈E(R1∪R2)滿足GR1[x→z]并且GR2[z→y]或者GR2[x→z]并且GR1[z→y]，則總有GR1∪R2[x→y].因此，由引理3知GR1[x→y]或GR2[x→y].這表明條件C2成立.

充分性. 令x,y∈E(R1∪R2)滿足GR1∪R2[x→y].記GR1∪R2中x到y(tǒng)的一個有向通路為

P0=(u0,u1)(u1,u2)…(uk-1,uk)，

其中u0=x且uk=y.不妨設(shè)(u0,u1)?GR1，并且令l(P0)表示P0中不在GR1中的有向邊的個數(shù).

先設(shè)條件C1成立，即

J(R1,R2)=[C(R1)∩D(R2)]∪[C(R2)∩D(R1)]=?.

如果l(P0)≠0，則存在整數(shù)0≤i≤k-2，使(ui,ui+1)?GR1且(ui+1,ui+2)?GR2，從而ui+1∈C(R1)∩D(R2)，與條件J(R1,R2)=?矛盾.因此，l(P0)=0，即P0?GR1，從而GR1[x→y].由引理3知結(jié)論成立.

再設(shè)條件C2成立.如果l(P0)≠0，即P0GR1，則存在整數(shù)1≤i≤k-1，使得

(u0,u1),(u1,u2),…,(ui-1,ui)?GR1, (ui,ui+1)?GR2.

這表明ui∈C(R1)∩D(R2)?J(R1,R2)滿足GR1[u0→ui]且GR2[ui→ui+1].因此，由條件C2知GR1[u0→ui+1]或GR2[u0→ui+1].不妨設(shè)GR1[u0→ui+1]，記GR1中u0到ui+1的一個有向通路為Q，則P1=Q∪P0[ui+1,uk]是GR1∪R2中u0到uk的一個有向通路，并且l(P0)=l(P1)+1.如果l(P1)≠0，則對P1繼續(xù)重復(fù)上面P0的過程.于是得到GR1∪R2中u0到uk的一個有向通路序列P0,P1,P2,…，滿足l(P0)>l(P1)>l(P2)>….由于l(P0)是一個非負(fù)整數(shù)，于是存在一個非負(fù)整數(shù)h，使l(Ph)=0，即Ph?GR1，從而GR1[x→y].由引理3知結(jié)論成立.

例1(i) 令X={1,2,3,4,5,6}，R1和R2是X上的兩個關(guān)系，其中R1和R2的關(guān)系圖如圖1和圖2所示.容易發(fā)現(xiàn)2∈C(R1)∩D(R2)={2,4}.顯然，GR1[1→2]且GR2[2→6]，但是在GR1和GR2中結(jié)點1都不能到達(dá)結(jié)點6，于是由定理3知t(R1∪R2)≠t(R1)∪t(R2).

圖1 GR1 圖2 GR2

(ii) 令R1和R2是 (i)中定義的兩個關(guān)系.記S1=R1∪{(2,6)}，S2=R2，則容易發(fā)現(xiàn)

J(S1,S2)=C(S1)∩D(S2)={2,4}.

顯然，GS1[1→2]且GS2[2→6]，亦有GS1[1→6]；GS1[1→4]且GS2[4→6]，亦有GS1[1→6].因此，S1和S2滿足定理3的條件C2，于是t(S1∪S2)=t(S1)∪t(S2).

起點和終點相同的有向通路稱為有向回路(環(huán)是特殊的有向回路).假設(shè)GR至少有兩個結(jié)點.對GR的任意不同結(jié)點x和y，如果GR[x→y]和GR[y→x]至少成立一個，則稱GR是單向連通的；如果GR[x→y]和GR[y→x]都成立，則稱GR是強連通的；如果GR的基礎(chǔ)圖(即忽略GR每個有向邊的方向后得到的無向圖)是連通的，則稱GR是弱連通的.弱連通分支的概念見[1，P129].約定只有一個結(jié)點且?guī)в协h(huán)的有向圖是強連通的(從而它也是一個弱連通分支).

定理4設(shè)R是有限集X上的關(guān)系，則t(s(R))=s(t(R))，當(dāng)且僅當(dāng)R滿足下面兩個條件：

C1:GR的每個非孤立的結(jié)點都包含在有向回路上；

C2:GR的每個非平凡的弱連通分支都是單向連通的.

證記GR中所有非平凡弱連通分支為GR1,GR2,…,GRk，其中Ri是對應(yīng)GRi的X上關(guān)系，則

R=R1∪R2∪…∪Rk.

(1)

(2)

(3)

因此，由式(2)-(3)和定理3之C1得

(4)

(5)

由定理1知

(6)

當(dāng)i≠j時，從E(Ri)∩E(Rj)=?知

(7)

于是由式(5)-(7)得

(8)

必要性. 設(shè)t(s(R))=s(t(R))，則從式(8)知

充分性. 設(shè)C1和C2都成立.

顯然，強連通有向圖的每個結(jié)點都包含在有向回路中并且強連通有向圖也是單向連通的，于是從定理4立即得到下面的推論.

推論設(shè)R是有限集X上的關(guān)系，如果GR是強連通的，則t(s(R))=s(t(R)).

3 結(jié) 論

本文利用關(guān)系圖的有關(guān)概念解決了文獻(xiàn)[3]中關(guān)系傳遞閉包的兩個遺留問題，即給出了有限集合X上關(guān)系R和F分別滿足t(R∪F)=t(R)∪t(F)和t(s(R))=s(t(R))的充分必要條件.這些結(jié)論有助于學(xué)生理解關(guān)系的閉包運算性質(zhì)和應(yīng)用，豐富了離散數(shù)學(xué)的教學(xué)內(nèi)容.

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