一类图逆半群的同余格的性质

罗天红，罗永乐，王正攀

西南大学 数学与统计学院， 重庆 400715

一直以来， 半群上的同余与同余格是国内外学者密切关注的对象(如文献[1-10]等)． 综述文献[6-7]较详尽地给出了20世纪关于半群的同余格的研究成果， 并指出了若干相关问题． 文献[1]首次介绍了顶点间最多有1条边的图的图逆半群， 并给出了这种图逆半群同余自由的充分条件． 文献[11]证明了： 顶点指数最多为1的连通图最多有1个汇点， 且若该图不是树， 则在圈共轭的意义下只有1个非平凡圈． 文献[9]建立了从图逆半群上的所有同余构成的集合到图的同余三元组构成的集合的一一对应． 文献[3]证明了： 图逆半群的同余格是上半模格， 但不是下半模格． 文献[4]应用有向图的性质， 证明了图逆半群上的0-受限同余所组成的集合关于包含关系形成一个分配格． 在这些基础之上， 本文利用文献[3]中的方法证明了： 顶点指数最多为1的连通图上的图逆半群的同余格不仅是上半模格， 还是下半模格．

有向图Γ=(V，E，r，s)由V，E以及E到V的映射r，s构成．V中的元素为顶点，E中的元素为边． 对于边e，s(e)为e的起点，r(e)为e的终点． 用|X|表示集合X的基数， 对任意顶点v， |s-1(v)|称为v的指数． 以下Γ=(V，E，r，s) 总表示某个有向图， 简记为Γ．

由V和E以及集合E*={e*：e∈E} 生成的满足以下各条的含零半群称为Γ上的图逆半群， 记为Inv(Γ)： 对任意u，v∈V，e，f∈E，

(G1)uv=δu，vu；

(G2)s(e)e=er(e)=e；

(G3)r(e)e*=e*s(e)=e*；

(G4)f*e=δf，er(e)．

在Γ中， 路是由边形成的序列α=e1e2…en， 其中r(ei)=s(ei+1)，i=1，2，…，n-1． 此时s(α)=s(e1)称为路α的起点，r(α)=s(en)称为路α的终点． 记{s(ei)：i=1，2，…，n}为u(α)， 约定顶点v为一条路径， 且u(v)=Ø． 若s(α)=r(α)， 且当i≠j时有s(ei)≠s(ej)， 则称α为圈． 我们用Path(Γ) 表示Γ中所有路构成的集合． 对于V1⊆V， 用C(V1) 表示所有满足u(c)⊆V1的圈构成的集合．

设H为V的子集， 若对任意e∈E， 当s(e)∈H时总有r(e)∈H， 则称H为V的遗传子集． 令H为遗传子集． 对任意v∈V， 称|{e∈E：s(e)=v，r(e)∉H}|为v相对于H的指数． 设W是V的子集， 且W中的元素相对于H的指数为1， 显然H∩W=Ø． 设f是C(V)到Z+∪{∞}的映射， 若对任意c∈C(H)， 有f(c)=1， 对任意c∉C(H)∪C(W)， 有f(c)=∞， 则称f为圈映射． 在文献[3]中，V的遗传子集H、 相对于H的指数为1的顶点集的子集W， 以及圈映射f构成Γ的一个同余三元组， 记为(H，W，f)． 用CT(Γ) 表示Γ的所有同余三元组构成的集合．

对任意m1，m2∈Z+∪{∞}， 我们用(m1，m2) 表示它们的最大公约数， [m1，m2]表示它们的最小公倍数， 且设Z+∪{∞}中的任意元素m都整除∞， 即(m， ∞)=m， [m， ∞]=∞．

根据文献[3]， 作者证明了图逆半群Inv(Γ)的同余格同构于CT(Γ) 关于以下二元关系形成的格： 对任意(H1，W1，f1)，(H2，W2，f2)∈CT(Γ)， (H1，W1，f1)≤(H2，W2，f2) 当且仅当H1⊆H2，W1H2⊆W2， 且对任意c∈C(V)，f2(c)|f1(c)．

在格L中， 我们用a∧b和a∨b分别表示a和b的上确界和下确界． 若a>b， 且在L中不存在元素x使得a>x>b， 则称a覆盖b， 记为a≻b或ba．

对L中任意元素a，b，c， 若有(a∨b)∧c=(a∧c)∨(b∧c)， 则称L为分配格；

对L中任意元素a，b，c，a≤c， 若有(a∨b)∧c=a∨(b∧c)， 则称L为模格；

对L中任意元素a，b， 若a≻a∧b，b≻a∧b时总有a∨b≻a，a∨b≻b， 则称L为上半模格； 对L中任意元素a，b， 若a∨b≻a，a∨b≻b时总有a≻a∧b，b≻a∧b， 则称L为下半模格．

本文引用文献[3] 对CT(Γ)中任意两个元素的上确界和下确界的刻画． 设

T1=(H1，W1，f1)T2=(H2，W2，f2)

是Γ的任意两个同余三元组． 我们用V0表示(W1∪W2)(H1∪H2)中相对于H1∪H2的指数为0的顶点形成的集合，X表示集合(W1∩W2)V0，J表示(W1∪W2)(H1∪H2)中存在以其为起点的满足条件u(α)⊆W1∪W2且以V0中某顶点为终点的路径α的顶点形成的集合．

定理1当图Γ为顶点指数最多为1的连通图时， 同余格(CT(Γ)， ≤)是下半模格．

证当Γ为顶点指数最多为1的连通图时， 由文献[11]的定理3.1知：Γ要么在不计循环置换的意义下只有1个圈， 要么最多有1个汇点(V中任意顶点都有路径到该点的顶点即为汇点)； 若H为V的非空遗传子集， 则H包含Γ的圈或汇点． 我们用ev表示从顶点v(v∈V)出发的边， 由Γ的定义，ev是唯一的． 则

V0={v∈W1H2：r(ev)∈H2}∪{v∈W2H1：r(ev)∈H1}

由于W1∩W2中的顶点相对于H1∪H2的指数为1， 故

X=W1∩W2

对T1=(H1，W1，f1)∈CT(Γ)，T2=(H2，W2，f2)∈CT(Γ)， 由文献[3]中引理2.7和引理2.8可得Tl=(Hl，Wl，fl)， 其中

Hl=H1∩H2Wl=(W1∩H2)∪(W2∩H1)∪X

对任意c∈C(V)，fl(c)=[f1(c)，f2(c)]．Tu=(Hu，Wu，fu)， 其中

Hu=H1∪H2∪JWu=(W1∪W2)Hu

对任意c∈C(V)，fu=(f1(c)，f2(c))． 要证明定理1， 即证明若有Tu≻T1，Tu≻T2， 则有T1≻Tl，T2≻Tl．

当H1=H2时， 据文献[3]的推论2.9 可知， 结论成立．

当H1≠H2时， 我们分H1⊂H2，H2⊂H1和H1H2且H2H1这3种情形讨论．

情形1H1⊂H2．

此时

Hu=H2∪JWu=(W1∪W2)(H2∪J)

H1可为空集， 但H2不能为空集， 则H2包含Γ的汇点或圈， 从而W2中无圈． 由圈映射的定义， 对任意c∈C(V)，f2(c) 取值为1， 故

fu(c)=(f1(c)，f2(c))=f2(c)fl(c)=[f1(c)，f2(c)]=f1(c)

情形1.1 当J=Ø时， 即Hu=H2．

由Tu≻T1，Tu≻T2以及文献[3]的引理2.1和引理2.3知，W1H2=Wu，W2⊆Wu且|WuW2|=1． 故有W2⊂Wu⊆W1， 从而

Tl=(H1， (W1∩H2)∪W2，f1)

因为

|W1Wl|=|W1[(W1∩H2)∪W2]|=|WuW2|=1

所以由文献[3]的引理2.3， 结论成立． 下证T2≻Tl．

对任意T′=(H′，W′，f′)∈CT(Γ)， 若有

(H2，W2，f2)>(H′，W′，f′)≥(H1， (W1∩H2)∪W2，f1)

(1)

则

H1⊆H′⊆H2

若H2=H′， 则W′⊆W2， 且由(1)式可得

[(W1∩H2)∪W2]H2=W2⊆W′

所以W′=W2， 进而f′=f2， 与假设矛盾， 所以H2≠H′．

由(1)式可知

[(W1∩H2)∪W2]H′⊆W′

所以(W1∩H2)H′中的顶点相对于H′的指数为1． 又由Wu=W1H2知，W1H2中顶点相对于H2的指数为1， 从而相对于H′的指数也为1 (V中任意顶点的指数最多为1)， 故(H′，W1H′，f2)∈CT(Γ)． 所以有

Tu=(H2，W1H2，f2)>(H′，W1H′，f2)≥(H1，W1，f1)

由Tu≻T1知H′=H1．

但若H1=H′， 由Tu≻T1和文献[3]的引理2.1知， 当c∈C[(W1∩H2)∪W2]时， 有

fu(c)=f1(c)=f2(c)

且在H2[H1∪(W1∩H2)∪W2]=H2(H1∪W1)中没有顶点相对于H1的指数为1． 又由于

H1⊂H2[(W1∩H2)∪W2]H2=W2

故由文献[3]的引理2.5得

W′=(W1∩H2)∪W2f′=f1

即T′=Tl． 从而有T2≻Tl．

情形1.2 当J≠Ø时， 即Hu=H2∪J．

此时H1⊂Hu，H2⊂Hu． 由Tu≻T1和文献[3]的引理2.1知

W1Hu=(W1∪W2)Hu

所以W2W1⊆J． 但在(H2∪J)(H1∪W1)中顶点相对于H1的指数为0， 所以W2W1中顶点相对于H1的指数为0， 从而相对于H2的指数为0， 由同余三元组的定义W2W1=Ø， 即有W2⊆W1． 类似地， 由Tu≻T2和文献[3]的引理2.1知

W1(W2∪H2)⊆JWu⊆W2

所以有

Wu⊆W2⊆W1

因为(H2∪J)(H2∪W2)中顶点相对于H2的指数为0， 所以

V0=W1(H2∪W2)

因此W2≠W1， 否则V0=Ø，J=Ø， 与假设矛盾． 所以

Wu⊆W2⊂W1

下证|V0|=1． 若|V0|>1， 对任意v1∈V0， 令

J1={v1}∪{v∈J： 存在α∈Path(Γ)， 使得s(α)=v，u(α)⊆W1，r(α)=v1}

由J1的定义不难看出H2∪J1是遗传子集． 若W2J1中存在顶点v相对于H2∪J1的指数为0， 因为Γ是连通图， 所以存在一条边以v为起点， 终点在J1中， 因此有v∈J1， 矛盾． 故W2J1中的顶点相对于H2∪J1的指数为1， 因此(H2∪J1，W2J1，f2)∈CT(Γ)． 所以有

(H2∪J，W1(H2∪J)，f2)>(H2∪J1，W2J1，f2)>(H2，W2，f2)

与Tu≻T2矛盾， 所以

|V0|=|W1(H2∪W2)|=1

由于

|W1Wl|=|W1[(W1∩H2)∪W2]|=|W1(H2∪W2)|=1

据文献[3]的引理2.3， 有

(H1，W1，f1)≻(H1， (W1∩H2)∪W2，f1)

即有T1≻Tl． 下证T2≻Tl．

对任意T′=(H′，W′，f′)∈CT(Γ)， 若有

(H2，W2，f2)>(H′，W′，f′)≥(H1， (W1∩H2)∪W2，f1)

(2)

则有

H1⊆H′⊆H2

若H′=H2， 则由(2)式可得

[(W1∩H2)∪W2]H2=W2⊆W′W′⊆W2

所以W′=W2， 进而f′=f2， 与假设矛盾． 所以H2≠H′． 故

H1⊆H′⊂H2

若以V0中的唯一的顶点为起点的边的终点在H′中， 则H′∪J是遗传子集． 由(2)式可得

[(W1∩H2)∪W2]H′⊆W′

因此W1H′中的顶点相对于H′的指数为1． 又因(W1∩H2)H′⊆H2， 且H2为遗传子集， 所以(W1∩H2)H′中的顶点相对于H′∪J的指数为1． 因为

H′∪J⊆H2∪J=Hu

故Wu中的顶点相对于H′∪J的指数也为1． 从而得到

(H′∪J，Wu∪[(W1∩H2)H′]，f2)∈CT(Γ)

且有

(H2∪J，Wu，f2)>(H′∪J，Wu∪[(W1∩H2)H′]，f2)>(H1，W1，f1)

这与Tu≻T1矛盾， 所以以V0中的唯一的顶点为起点的边的终点在H2H′中． 于是(H′，W1H′，f1)∈CT(Γ)， 且有

(H2∪J，Wu，f2)>(H′，W1H′，f1)≥(H1，W1，f1)

再由Tu≻T1知H′⊆H1．

由(2)式和文献[3]的引理2.5 知[(W1∩H2)∪W2]=W′， 进而f′=f2．T2≻Tl得证．

情形2H2⊂H1．

与情形1的证明类似．

情形3H1H2且H2H1．

此时H1≠Ø，H2≠Ø， 故若Γ中有圈， 则圈在H1∩H2中， 所以W1和W2中均无圈． 从而可设

fu=f1=f2=fl=f． 由Tu≻T1，Tu≻T2以及文献[3]的引理2.1可得

V0=[W1(H2∪W2)]∪[W2(H1∪W1)]

下证V0=Ø． 否则， 不妨设W2(H1∪W1)≠Ø． 令

J2={v∈J： 存在α∈Path(Γ)， 使得s(α)=v，u(α)⊆W1∪W2，r(α)∈W2(H1∪W1)}

则J2≠Ø． 由Tu≻T1和文献[3]的引理2.1知，W2(H1∪W1)中的顶点相对于H1的指数为0， 所以H1∪J2为遗传子集． 类似于情形1.2的证明，W1J2中的顶点相对于H1∪J2的指数为1， 所以(H1∪J2，W1J2，f)∈CT(Γ)． 因此

(H1∪H2∪J，Wu，f)>(H1∪J2，W1J2，f)>(H1，W1，f1)

这与Tu≻T1矛盾， 故V0=Ø．

由V0=Ø及J的定义可得J=Ø， 所以

W1=(W1∩H2)∪(W1∩W2)W2=(W2∩H1)∪(W1∩W2)

Tu=(H1∪H2，W1∩W2，f)Tl=(H1∩H2，W1∪W2，f)

下证T1≻Tl． 对任意T′=(H′，W′，f′)∈CT(Γ)， 若有

(H1，W1，f)>(H′，W′，f′)≥(H1∩H2，W1∪W2，f)

(3)

则有H1∩H2⊆H′⊆H1． 若H′=H1， 由(3)式可得

(W1∪W2)H′=W1⊆W′W′⊆W1

所以W′=W1． 进而f′=f， 与假设矛盾， 所以H′≠H1． 故H1∩H2⊆H′⊂H1， 进而有

H2⊆H′∪H2⊂H1∪H2

由(3)式可知(W1∪W2)H′⊆W′， 所以W2H′⊆W′， 这说明在W2H′中的顶点相对于H′的指数为1． 又因为H′∪H2是遗传子集． 所以(H′∪H2，W2H′，f)∈CT(Γ)． 由

Tu>(H′∪H2，W2H′，f)≥(H2，W2，f2)

得H2=H′∪H2， 即H′⊆H2． 又由H′⊆H1， 所以H′⊆H1∩H2． 故H′=H1∩H2． 与情形1.1的证明类似， 由文献[3]的引理2.5得

W′=W1∪W2f′=f

即T′=Tl，T1≻Tl得证． 同理可证T2≻Tl．