離散數學教材中傳遞閉包的兩個問題

譚尚旺， 寧文杰

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

1 引 言

文中未定義的概念和記號見文獻[1].離散數學是信息類學科的重要基礎課，關系是離散數學的重要內容之一.各類離散數學教材都詳細討論了關系的各種閉包運算(例如，文獻[1-3]).

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

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

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

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

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

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

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

2 結論及其證明

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

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

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

(x,y)∈t(R)?存在一個正整數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的一個有向通路

?GR[x→y].

引理3設R1和R2是有限集X上的兩個關系，則t(R1∪R2)=t(R1)∪t(R2)，當且僅當對任意的x,y∈E(R1∪R2)，當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)

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

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

?當GR1∪R2[x→y]時，都有GR1[x→y]或GR2[x→y].

定理3設R1和R2是有限集X上的兩個關系，記

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

則t(R1∪R2)=t(R1)∪t(R2)，當且僅當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].

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

假設條件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的一個有向通路為

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

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

先設條件C1成立，即

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

如果l(P0)≠0，則存在整數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知結論成立.

再設條件C2成立.如果l(P0)≠0，即P0GR1，則存在整數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].不妨設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繼續重復上面P0的過程.于是得到GR1∪R2中u0到uk的一個有向通路序列P0,P1,P2,…，滿足l(P0)>l(P1)>l(P2)>….由于l(P0)是一個非負整數，于是存在一個非負整數h，使l(Ph)=0，即Ph?GR1，從而GR1[x→y].由引理3知結論成立.

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

圖1 GR1 圖2 GR2

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

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).

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

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

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

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

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

R=R1∪R2∪…∪Rk.

(1)

(2)

(3)

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

(4)

(5)

由定理1知

(6)

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

(7)

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

(8)

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

充分性. 設C1和C2都成立.

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

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

3 結 論

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

致謝作者感謝相關文獻對本文的啟發以及審稿專家提出的寶貴意見！