离散数学中关系交与复合的传递闭包

谭尚旺， 宁文杰

(中国石油大学(华东) 理学院， 山东 青岛266580)

1 引 言

对集合X上的关系R和F,令D(R)和C(R)分别表示R的定义域和值域,R∘F表示R与F的复合，Rk表示k个R的复合，t(R)表示R的传递闭包. 文中未定义的概念和记号见文献[1-2].

离散数学是信息类学科的重要基础课，关系是离散数学的重要内容之一. 各类离散数学教材都详细讨论了关系的闭包运算(例如，文献[1-3]). 在关系的各种闭包运算中以传递闭包的计算最为复杂和困难. 因此，大量文献对传递闭包的计算方法和应用进行了讨论，而关于传遍包与关系其它运算之间联系的讨论则较少. 许多文献都给出了下面一个结论(例如，文献[1]).

定理1设R和F是集合X上两个关系，则t(R∪F)⊇t(R)∪t(F).

由定理1知t(R∪F)⊆t(R)∪t(F)等价于t(R∪F)=t(R)∪t(F). 因此，在学习离散数学课程中，学生问及下面的问题：

问题1设R和F是集合X上两个关系，问是否存在使t(R∪F)=t(R)∪t(F)成立的非平凡充分必要条件？

受问题1的启发，学生进一步问及下面两个问题：

问题2设R和F是集合X上两个关系，问是否存在使t(R∩F)=t(R)∩t(F)成立的非平凡充分必要条件？

问题3设R和F是集合X上两个关系，问是否存在使t(R∘F)=t(R)∘t(F)成立的非平凡充分必要条件？对任意正整数m,是否存在使t(Rm)=[t(R)]m成立的非平凡充分必要条件？

尽管目前离散数学教材、教学参考书和涉及关系传递闭包的论文很多，但遗憾的是没有发现上述问题的任何答案. 因此，为解除学生学习上的疑惑和丰富离散数学的教学内容，在[4]中已经对问题1给出了回答. 本文将利用关系图的有关概念给出问题2和问题3的回答.

2 结论及其证明

引理1[1]设R和F是集合X上两个关系. 如果R⊆F,则t(R)⊆t(F).

令GR表示有限集X上关系R的关系图，(a,b)表示GR中起点为a且终点为b的唯一有向边(特别是(a,a)表示结点a处的环).GR中有向边的序列P=(u0,u1)(u1,u2)…(uk-1,uk)称为结点u0到结点uk的一个有向通路(简称为通路)，其中P中有向边的个数称为通路P的长度. 如果GR中存在结点x到结点y的通路，则称x可达y,并且记为GR[x→y].

引理3[4]设R是有限集X上关系且x,y∈X,则(x,y)∈t(R),当且仅当GR[x→y].

定理2设R和F是有限集X上的两个关系，则t(R∩F)=t(R)∩t(F),当且仅当对任意的x∈D(R∩F)且y∈C(R∩F),当GR[x→y]且GF[x→y]时，都有GR∩F[x→y].

证用A⟺B表示命题A成立当且仅当命题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). 因此，依次由子集定义、交运算定义和引理3得

t(R∩F)=t(R)∩t(F) ⟺t(R)∩t(F)⊆t(R∩F)

⟺当(x,y)∈t(R)∩t(F)时，都有(x,y)∈t(R∩F)

⟺当(x,y)∈t(R)且(x,y)∈t(F)时，都有(x,y)∈t(R∩F)

⟺当GR[x→y]且GF[x→y]时，都有GR∩F[x→y].

例1令X={1,2,3,4,5,6},R和F是X上关系，其中R,F和R∩F的关系图分别如图1—图3所示. 显然，D(R∩F)={1,2,4},C(R∩F)={2,3,5,6}.易发现GR[2→6]并且GF[2→6],但是GR∩F中2不能到达6,于是由定理2知t(R∩F)≠t(R)∩t(F).

图1 GR 图2 GF 图3 GR∩F

令R和F是有限集X上的两个关系，x∈D(R)且y∈C(F). 如果GR∪F中存在x到y的一个通路

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个有向边分别依次交错的出现在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关于GR和GF边交错到y的通路且称GR∪F中x关于GR和GF边交错可达y.

定理3设R和F是有限集X上两个关系，则t(R∘F)=t(R)∘t(F),当且仅当R和F满足下面两个条件之一：

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

C2:C(R)∩D(F)≠∅,并且对任意的x∈D(R),y∈C(F),在GR∪F中x关于GR和GF边交错可达y⟺存在一个元素z∈C(R)∩D(F),使GR[x→z]且GF[z→y].

证必要性 假设C1不成立，下面证明C2成立. 令x∈D(R)且y∈C(F),则依次由边交错可达定义、边交错通路定义、关系复合定义、引理2和条件t(R∘F)=t(R)∘t(F)、引理3得

在GR∪F中x关于GR和GF边交错可达y

⟺GR∪F中存在x关于GR和GF边交错到y的通路

(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].

充分性 依次由关系定义域、值域和复合运算定义，容易验证

D(S)=D(t(S)),C(S)=C(t(S)),S∈{R,F};R∘F=∅ ⟺C(R)∩D(F)=∅.

因此，当条件C1成立，即C(R)∩D(F)=∅时，t(R∘F)=∅=t(R)∘t(F).

下面设条件C2成立. 令(x,y)∈t(R∘F),则由引理3知GR∘F[x→y],于是由结点可达的定义知GR∘F中存在x到y的一个通路(x,z1)(z1,z2)(z2,z3)…(zk-1,y),从而由关系图的定义知

(x,z1),(z1,z2),(z2,z3),…,(zk-1,y)∈R∘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关于GR和GF边交错到y的一个通路. 因此，由假设条件知存在一个元素z∈X,使GR[x→z]且GF[z→y],从而由引理3知(x,z)∈t(R),(z,y)∈t(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设X={1,2,3,4,5,6},R和F是X上的两个关系，其中R,F和R∪F的关系图分别如图4—图6所示. 容易发现

图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)的元素共构成16个有序结点对，其中

1与2, 2与3, 2与5, 3与4, 5与4, 2与2, 3与3, 5与5

中的每个有序结点对x与y,在GR∪F中显然没有x关于GR和GF边交错到y的通路，并且也不存在元素z∈C(R)∩D(F),使GR[x→z]并且GF[z→y].

令PJ[x,y]表示GR∪F中x关于GR和GF边交错到y的一个通路，PR[x,y]表示GR中x到y的一个通路，则对有序结点对

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设R是有限集X上关系，则对整数m≥2,都有t(Rm)⊆[t(R)]m.

证令(x,y)∈t(Rm),则由引理2知存在正整数k,使(x,y)∈(Rm)k=Rmk. 由关系复合定义知存在元素x1,x2,…,xmk-1∈X,使

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

因此，由关系图的定义知

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

是GR中x到y的一个通路，从而

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

于是由关系复合的定义知(x,y)∈[t(R)]m. 这就证明了结论t(Rm)⊆[t(R)]m.

定理4设R是有限集X上关系且m≥2,则t(Rm)=[t(R)]m,当且仅当对任意的x∈D(R)且y∈C(R),当GR中存在x到y长≥m+1的通路时，GR中都存在x到y长为m正整数倍的通路.

证必要性 令

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

是GR中x到y的长为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).

由关系复合的定义知(x,y)∈[t(R)]m. 由假设条件t(Rm)=[t(R)]m知(x,y)∈t(Rm). 由引理2知存在正整数k,使(x,y)∈(Rm)k=Rmk. 由关系复合定义知存在元素z1,z2,…,zmk-1∈X,使

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

于是由关系图定义知

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

是GR中x到y的长为km的通路.

充分性 令(x,y)∈t(R)m,则由关系复合的定义知存在元素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的一个通路，则P0P1…Pm-1是GR中x到y的一个长为s(s≥m)的通路. 不妨设s≥m+1(否则，下面的k取1)，则由假设条件知GR中存在x到y的长为km的通路

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

这等价于

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

于是由关系复合得定义知(x,y)∈Rkm=(Rm)k,从而由引理2知(x,y)∈t(Rm). 这就证明了t(Rm)⊇[t(R)]m. 因此，由引理4知t(Rm)=[t(R)]m.

推论1设R是有限集X上自反的关系，则对整数m≥2,都有t(Rm)=[t(R)]m.

证令

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

推论2设R是有限集X上传递的关系，则对整数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中结点x到结点y的长为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的长为m的通路. 因此，由定理4知t(Rm)=[t(R)]m.

设R是n(n≥3)元集合X上的关系且GR是有向树. 由有向树的定义知R是反自反、反对称、反传递的，并且当GR[x→y]时，x到y的通路是唯一的且是基本通路. 用l(R)表示GR中最长通路的长度，则1≤l(R)≤n-1. 如果l(R)=1,则存在a∈X,使得R={(a,b)∶b∈X-{a}}或者R={(b,a)∶b∈X-{a}},此时对任意整数m≥2,容易发现都有t(Rm)=∅=[t(R)]m.

推论3设R是有限集合X上的关系，其中GR是有向树并且l(R)≥2,则当m≥l(R)时，都有t(Rm)=[t(R)]m,当2≤m

证当m≥l(R)时，对任意的x,y∈X,由l(R)定义知GR中没有x到y的长≥m+1的通路，于是由定理4知t(Rm)=[t(R)]m. 当2≤m

3 结 论

利用关系图的有关概念解决了各类离散数学教材中传递闭包的几个遗留问题，即确定了有限集合X上关系R和F分别满足

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

的充分必要条件. 特别是当R是自反的或传递的时证明了t(Rm)=[t(R)]m成立，并且当GR是有向树时也确定了使t(Rm)=[t(R)]m成立的m的所有取值(该结论显然当GR是有向森林时也成立). 这些结论揭示了关系传递闭包与关系交与复合运算之间的内在联系，有助于学生理解关系的运算性质和应用，丰富了离散数学的教学内容.

致谢作者感谢相关文献对本文的启发以及审稿专家提出的宝贵意见！